Avec quelle efficacité l'algorithme NextPermutation peut-il générer des permutations ?

Génération de permutations la plus efficace

Générer toutes les permutations d'un ensemble est un problème classique en informatique. Bien qu’il existe différents algorithmes, atteindre une efficacité optimale reste un défi. Cet article explore l'algorithme NextPermutation, l'une des approches les plus efficaces.

L'algorithme NextPermutation

L'algorithme NextPermutation, initialement proposé par Edwin Knuth, fonctionne comme suit :

1. Identifiez le plus grand index j tel que a[j] < une[j 1]. Si aucun index de ce type n'existe, la permutation actuelle est la dernière.
2. Trouvez le plus grand index l tel que a[j] < a[l].
3. Échangez a[j] et a[l].
4. Inversez la partie du tableau de l'index j 1 à la fin, réinitialisant ainsi son ordre lexicographique.

Mise en œuvre et efficacité

L'algorithme NextPermutation peut être implémenté avec les étapes suivantes :

public static bool NextPermutation(int[] numList)
{
    int largestIndex = -1;
    for (int i = numList.Length - 2; i >= 0; i--)
    {
        if (numList[i] < numList[i + 1])
        {
            largestIndex = i;
            break;
        }
    }

    if (largestIndex < 0) return false;

    int largestIndex2 = -1;
    for (int i = numList.Length - 1; i >= 0; i--)
    {
        if (numList[largestIndex] < numList[i])
        {
            largestIndex2 = i;
            break;
        }
    }

    int tmp = numList[largestIndex];
    numList[largestIndex] = numList[largestIndex2];
    numList[largestIndex2] = tmp;

    for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--)
    {
        tmp = numList[i];
        numList[i] = numList[j];
        numList[j] = tmp;
    }

    return true;
}
En utilisant cet algorithme, itérer sur toutes les permutations d'un tableau de taille 11 prend beaucoup moins de temps qu'avec l'algorithme précédent. Le temps exact dépend de l'implémentation et du matériel spécifiques, mais l'amélioration est perceptible.
Optimisation pour la vitesse
D'autres optimisations sont possibles pour améliorer la vitesse de NextPermutation algorithm :


Optimisation de l'accès au tableau : Utilisation d'une variable pour stocker numList.Length au lieu de y accéder à plusieurs reprises peut améliorer les performances.

Élimination des échanges inutiles : Lorsque l'algorithme inverse la queue du tableau, il est possible d'ignorer l'échange des premiers éléments de l'indice 1 les plus grands.
 Utilisation d'un type d'index non signé : Le choix d'un type d'index non signé (uint) peut empêcher erreurs de dépassement d'entier.

En appliquant ces optimisations, l'algorithme peut être encore accéléré, réduisant ainsi le temps nécessaire pour générer des permutations pour des tableaux plus grands.
Conclusion
L'algorithme NextPermutation, combiné à des optimisations, fournit un moyen très efficace de générer des permutations d'un ensemble. Sa rapidité et sa simplicité en font un outil précieux pour diverses applications impliquant des problèmes combinatoires et la génération de permutations.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!