Comment générer toutes les permutations d'un tableau, y compris celles comportant des éléments répétés ?

Générer toutes les permutations d'un tableau

Étant donné un tableau d'éléments distincts, le but est de lister toutes les permutations possibles des éléments du tableau.

Algorithme

L'algorithme suivant génère toutes les permutations en temps O(N!) complexité :

1. Initialiser : Définir i = 0.
2. Itérer sur le tableau : Tandis que i est inférieur à la longueur du tableau :
3. Échange : Échangez l'élément à l'index i avec chacun des éléments restants dans le tableau.
4. Recurse : Appelez récursivement l'algorithme avec i 1 comme nouvelle valeur i.
5. Échangez en arrière : Après l'appel récursif, replacez l'élément dans sa position d'origine.
6. Incrémentation i : Incrémentez i de 1.

Implémentation Python

def permute(arr, i=0):
    if i == len(arr) - 1:
        print(arr)
        return

    for j in range(i, len(arr)):
        arr[i], arr[j] = arr[j], arr[i]
        permute(arr, i + 1)
        arr[i], arr[j] = arr[j], arr[i]

Algorithme Jarvis March

Pour les tableaux avec des éléments répétés, l'algorithme Jarvis March est une approche plus efficace :

1. Tri : Trier le tableau par ordre croissant ordre.
2. Pendant que : Tant que ce n'est pas fait :
3. Trouver le pivot : Trouver le plus grand index où l'élément est inférieur à son successeur.
4. Rechercher adjacent : Rechercher le dernier élément de la partie triée qui est supérieur à l'élément au niveau du pivot index.
5. Échanger : Échanger les éléments au niveau du pivot et des indices adjacents.
6. Inverser : Inverser les éléments de l'index pivot jusqu'à la fin de la partie triée.
7. Vérification effectuée : Vérifiez si le tableau est trié par ordre décroissant. Si tel est le cas, quittez la boucle.

Implémentation Python

def permute_repeated(arr):
    ind = [0] * len(arr)
    for i in range(len(arr)):
        ind[i] = i

    while True:
        yield [arr[i] for i in ind]

        for i in range(len(arr) - 2, -1, -1):
            if ind[i] < ind[i + 1]:
                break

        if i == -1:
            return

        for j in range(len(arr) - 1, -1, -1):
            if arr[j] > arr[i]:
                ind[i], ind[j] = ind[j], ind[i]
                break

        ind[i + 1:] = sorted(ind[i + 1:])

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!