Maison > développement back-end > C++ > Comment puis-je générer toutes les permutations d'un tableau ?

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

Mary-Kate Olsen
Libérer: 2024-12-18 02:27:17
original
422 Les gens l'ont consulté

How Can I Generate All Permutations of an Array?

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 :

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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]

Copier après la connexion

Exemple d'utilisation :

1

2

3

arr = [3, 4, 6, 2, 1]

permutations = generate_permutations(arr)

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

Copier après la connexion

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!

source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal