Comment puis-je générer toutes les permutations d'un tableau ?

Génération de permutations d'un tableau

La permutation d'un tableau comprend un arrangement unique de ses éléments. Pour un tableau à N éléments, il existe N ! (Ffactorielle N) permutations distinctes. Cette question vise à décrire un algorithme pour générer ces permutations.

Algorithme :

Considérez les étapes suivantes pour générer des permutations de tableau :

1. Initialiser : Commencez par prendre le premier élément comme pivot et placez-le dans la première position du courant liste de permutation.

2. Permutation récursive : Parcourez les éléments restants du tableau. Échangez chaque élément avec le pivot, appelez la fonction de permutation de manière récursive avec le pivot mis à jour à la position suivante et échangez à nouveau pour restaurer l'ordre d'origine.

   • Par exemple, étant donné {3,4,6, 2,1} avec le pivot 3, vous parcourez {4,6,2,1}. Vous échangez 4 avec 3, permutez récursivement {4, 3, 2, 1} avec le pivot 4 et revenez en arrière.
3. Terminaison : Lorsque la boucle atteint le dernier élément, la liste de permutation actuelle est complète. Sortez-le.

Implémentation :

Voici une implémentation Python de l'algorithme ci-dessus :

def generate_permutations(arr):
  perms = []
  _generate_permutations_helper(arr, 0, perms)
  return perms


def _generate_permutations_helper(arr, start, perms):
  if start == len(arr) - 1:
    perms.append(arr.copy())
  else:
    for i in range(start, len(arr)):
      arr[start], arr[i] = arr[i], arr[start]
      _generate_permutations_helper(arr, start + 1, perms)
      arr[start], arr[i] = arr[i], arr[start]

Exemple d'utilisation :

arr = [3, 4, 6, 2, 1]
permutations = generate_permutations(arr)
print(permutations)  # [[3, 4, 6, 2, 1], [3, 4, 2, 6, 1], ... ]

Remarque : Cette méthode peut être optimisée pour l'utilisation de la mémoire en conservant uniquement les éléments de début et de fin des permutations actuelles et en construisant la liste complète uniquement à la fin, éliminant ainsi le besoin de conserver la liste complète des permutations en mémoire.

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!