Permutations

**Pépé Lélé** · 16/11/2005, 15h45

Bonjour,

J'aimerais connaître le code d'une fonction qui permet à partir d'un ensemble de n élements (qui se trouvent dans un tableau) de construire un tableau (ou un arbre, ou tout auter suggestion !) contenant toutes les permutations possibles à partir de ces n élements (que l'on peut supposer différents, pour que ce soit plus simple).

Il y a n*(n-1)*(n-2)*...*1=n! permutations dans ce cas là.

J'ai cherché sur le net le code d'une telle fonction, mais je ne l'ai pas trouvé.

J'ai besoin de cette fonction pour n=6 (soit 720 permutations).

Si quelqu'un pouvait me fournir un lien fournissant une telle fonction, à défaut du code, merci.

un petit exemple : si n=4, avec t={'a','b','c','d'}

on a :
a b c d
a b d c
a d b c
a d c b
a c d b
a c b d
d a c b
... (24 permutations en tout).

**Trap D** · 16/11/2005, 17h29

Envoyé par Pépé Lélé

Bonjour,
J'ai cherché sur le net le code d'une telle fonction, mais je ne l'ai pas trouvé.

Tu as mal cherché sur ce forum, c'est l'objet de topics de manière très régulière

**Pépé Lélé** · 16/11/2005, 17h54

C'est vrai que j'ai trouvé plusieurs fois cette question (rien que sur ce site), quant aux réponses ... elles ne sont pas satisfaisantes, c'est pourquoi je demande à nouveau.

**Matthieu Brucher** · 16/11/2005, 18h01

Tu mets tous tes éléments dans une liste, puis tu boucles.
Pour chaque élément du tableau, tu mets le premier élément dans la liste, puis tu appliques la méthode au reste du tableau, puis tu mets le deuxième élément et tu appliques la méthode au reste du tableau, ...

**Trap D** · 16/11/2005, 18h19

J'ai bien les procédures récursives, tu peux essayer celà, ça marche bien.
Evidemment, s'il y beaucoup de lettres, tu peux faire exploser ta machine.
C'est une construction progressive de la chaine, str1 contient l'anagramme déjà formé, str2 les lettres restant à introduire.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
procédure permutation(chaine str1, chaine str2)
   variables
      ch : caractère
      i : entier (compteur de boucle)
      str11 : chaine de caractères
      str22 : chaine de caractères
debut      
   si longueur(str2) = 0 alors
      ajouter str1 à la liste des permutations
   sinon
      pour chaque lettre i de str2 faire
      debut
         ch <- ième lettre de str2
         str11 <- str1 + ch
         str22 <- str2 - ch
         permutation(str11, str22)
	  fin
   fin si
fin

Appel par permutation("", "abcd").

**Pépé Lélé** · 18/11/2005, 19h01

Merci

**xorsx** · 20/12/2006, 19h17

auriez vous un ordre d'idée de la complexité d'un telle fonction (la fonction juste au dessus) ?

merci

**millie** · 20/12/2006, 23h07

Si tu as un processeur d'500 Mhz qui réalise une permutation par cycle (c'est une approximation) :

Pour générer toutes les permutations de 12 éléments, il te faut 1 seconde (12! ~ 500.000.000). Donc, il suffirait de monter à 18 éléments pour voir qu'il faut : 13.366.080 sec = 154 jours...

Avec 20 éléments => 161 ans

Permutations

Algorithmes et structures de données

Discussions similaires

Partager

Partager