Discussion :

[c-candide]

Bonjour

Je m'intéresse à la question d'écrire un programme en C pour d'afficher tous les anagrammes d'une chaîne donnée, par exemple, il y a 6 anagrammes de PAPA :

PAPA, APPA, AAPP, PPAA, PAAP, APAP

Mais restons-en aux permutations de n lettres (donc deux à deux distinctes). Je ne m'intéresse pas à un algorithme itératif (l'ordre lexicographique par exemple) mais à un algorithme récursif surtout que cela semble assez adapté à la notion de permutation et de factorielle.

[Au passage, j'ai assez rapidement regardé le fascicule de Knuth et il ne parle pas explicitement me semble-t-il d'algorithme récursif (il en parle pour énumérer les tris topologiques).]

Ainsi, une idée assez naturelle est la suivante:

pour avoir toutes les permutations sur (n+1) lettres il suffit de connaitre toutes les permutations sur les n premières et pour chacune d'elle, interposer la dernière
lettre entre deux lettres (ou une seule aux extrémités) du mot à n lettres. Exemple : les permutations sur 2 lettres sont :
AB
BA
donc pour avoir celles sur A, B et C, je prends la première permutation AB et j'interpose de trois façons la nouvelle lettre C, ce qui donne
CAB
ACB
ABC
et puis on fait de même avec l'autre permutation BA et on obtient ainsi les 6 permutations de A, B, C.

Il y a aussi une autre idée assez naturelle, c'est qu'une fois connues les permutation sur n objets, on consruit les permutations sur (n+1) objets en faisant des échanges (transposition) entre la nouvelle lettre et les anciennes. Illustration :
ABC
BAC
CBA (A<->C)
BCA (A<->C)
ACB (A<->B)
CAB (A<->B)

En théorie c'est bien mais dans la pratique (à implémenter), il me semble que cela nécessite la mémorisation de toutes les permutations sur les n dernières lettres et vu le nombre de permutations, vaut mieux stocker ça dans un fichier qu'en RAM.... Maintenant quelqu'un voit-il une astuce, suivant toujours cette idée d'interposition ou de transposition (parce je sais le faire avec une autre méthode), pour engendrer les permutations à la volée (sans mémoriser ci ce n'est O(n) objets) ?

[pseudocode]

Maintenant quelqu'un voit-il une astuce, suivant toujours cette idée d'interposition ou de transposition (parce je sais le faire avec une autre méthode), pour engendrer les permutations à la volée (sans mémoriser ci ce n'est O(n) objets) ?

Tu peux definir un ordre lexicographique sur les matrices de permutation. A partir de la, tu peux generer la matrice "suivante" uniquement a partir de la matrice courante. Dans l'implémentation, ce n'est pas utile de stocker la matrice en mémoire, mais juste son numero d'ordre.

[c-candide]

Tu peux definir un ordre lexicographique sur les matrices de permutation.

Tu parles des matrices de permutation au sens mathématiques, cad à la (0,1)-matrice définie à l'aide du symbole de Kronecker ? Bon de toute façon une matrice de permutation (au sens précédent) et une permutation c'est la même chose, donc tu dois vouloir dire autre chose.

A partir de la, tu peux generer la matrice "suivante" uniquement a partir de la matrice courante. Dans l'implémentation, ce n'est pas utile de stocker la matrice en mémoire, mais juste son numero d'ordre.

Je veux bien qu'on numérote les permutations (mais si n est grand on risque de ne pas avoir assez de bits pour la représenter) et d'ailleurs c'est ce qu'on fait avec l'algo itératif habituel (l'ordre lexicographique sur les mots permutés) mais je ne comprends pas où tu veux en venir, ce que tu dis ça s'applique à mon algorithme récursif ? comment tu fais pour ne pas stocker toutes les permutations du rang n pour avoir celles au rang suivant ? Tu peux illustrer pour n=3 ?

[pseudocode]

comment tu fais pour ne pas stocker toutes les permutations du rang n pour avoir celles au rang suivant ? Tu peux illustrer pour n=3 ?

Au lieu de faire une formulation récursive sur l'ensemble de données, tu peux faire une formulation récursive sur la matrice de permutation et faisant une décomposition en produit de cycles.

Par exemple, tu peux fixer le 1er element et faire une permutation sur les N-1 elements restants (d'ou la recursion).

Code :

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

1
2
3
4
5
 
P({}) = {}
 
P(E) = Union { {x} o P(E\x) }
       x dans E

(cf lien sur wikipedia)

par exemple:
P({1,2,3}) = {{1}oP({2,3}) U {2,P({1,3}) U {3,P({1,2})
= {1 o ({2,3) U (3,2)) + {2 o ({1,3) U (3,1)) + {3 o ({1,2) U (2,1))
= {1,2,3} U {1,3,2} U {2,1,3} U {2,3,1} U {3,1,2} U {3,2,1}

Maitenant, on peut definir un numero d'ordre pour chacun de ces elements. Par exemple le n° de l'element {x} dans l'ensemble pour chaque profondeur de la récursion. Ce numero "K" varie entre 0 et (n!-1).

par exemple, pour l'ensemble {1,2,3}
Permutation #0: {1, 2, 3}
Permutation #1: {1, 3, 2}
Permutation #2: {2, 1, 3}
Permutation #3: {2, 3, 1}
Permutation #4: {3, 1, 2}
Permutation #5: {3, 2, 1}

Pour retrouver les n° des elements {x} a partir de "K" il suffit de faire des divisions euclidiennes successives. Le calcul d'une permutation quelconque necessite un nombre constant de "n" divisions.

exemple K=5:
5 / factoriel(3-1) = 5/2 = 2 reste 1 ---> {1, 2, "3"}
1 / factoriel(2-1) = 1/1 = 1 reste 0 ---> {1, "2"}
0 / factoriel(1-1) = 0/1 = 0 reste 0 ---> {"1"}

Code java :

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
public class Permutations {
 
	static String[] list = new String[]{"A","B","C","D"};
 
	static int[] divisor = null;
 
	// genere la permutation numero #k
	public static List<String> generate(int k) {
		List<String> copy   = new ArrayList<String>(Arrays.asList(list));
		List<String> result = new ArrayList<String>();
 
		int number = k;
		for(int d=list.length;d>=1;d--) {
			int index = number/divisor[d];
			number = number % divisor[d];
			result.add( copy.remove(index) );
		}
 
		return result;
	}
 
 
	public static void main(String[] args) {
		// rang = longueur de la liste
		int n = list.length;
 
		// diviseur pour chaque rang = factoriel(rang-1)
		divisor = new int[n+1];
		divisor[1]=1;
		for(int i=2;i<=n;i++) divisor[i]=(i-1)*divisor[i-1];
 
		// nombre de permutations: factoriel(rang)
		int factoriel = 1;
		for(int i=1;i<=n;i++) factoriel*=i;
 
		// genere toutes les permutations
		for(int k=0;k<factoriel;k++) {
			List<String> result = generate(k);
			System.out.println(k+": "+result);
		}
	}
}

[c-candide]

Quand je disais

suivant toujours cette idée d'interposition ou de transposition (parce je sais le faire avec une autre méthode)

je voulais parler justement de cette méthode

P({1,2,3}) = {{1}oP({2,3}) U {2,P({1,3}) U {3,P({1,2})

Ensuite, ton implémentation diffère largement de la mienne (à cause de cette méthode de numérotation par "tranches" de k!, je vois bien l'idée mais il y a quelques détail d'implémentation qui me sont pas encore un peu flous), ce que tu as codé semble plus simple (le code est nettement plus court) mais ma méthode traite plus généralement du cas des anagrammes (répétitions de lettres autorisées) et je ne crois pas que ce soit le cas de la tienne. En plus, je ne connais pas le C++ (le new c'est comme malloc ?) (cf. le EDIT ci-dessous) donc j'ai du mal à me rendre compte de ton implémentation et en particulier du point qui m'intéresse le plus ici, à savoir la gestion de la mémoire (ton fichier est complet compilable ? y'a pas des en-têtes à placer au cas où je voudrais tester ?).


Sinon, je suis un peu gêné de te dire que ça ne répond pas vraiment à ma question puisque je parlais d'un autre algorithme basé sur l'insertion du nouvel item à toutes les places possibles de chaque permutation d'ordre immédiatement inférieur, cf. mon exemple dans le post ci-dessus.

Au passage, tu parles de décomposition en cycles et ça me fait penser qu'il y aurait peut-être une méthode de génération des permutations qui consisterait à les générer par l'expression de leurs décompositions en cycles, ce qui semble faisable, il faut commencer par déterminer les partitions de n (ce qui est assez facile) et puis savoir générer les combinaisons (ça va encore), la suite paraît un peu plus compliquée à écrire.

Merci de ta réponse que je vais maintenant examiner en détail.
______________
EDIT
(1) Bon, je crois que je me suis planté en parlant de C++, c'est plutôt du java, tu te doutes donc que je ne connais pas non plus et en plus, comme java gère lui-même la mémoire, je ne vais pas être avancé. Moi, je ne connais que le C.

(2) D'autre part, ton algorithme ne me semble pas récursif, cf ce que je disais :

Je ne m'intéresse pas à un algorithme itératif (l'ordre lexicographique par exemple) mais à un algorithme récursif

(3) Combien de temps CPU mets-tu pour passer en revue le cas n=12 ?

[pseudocode]

(1) Bon, je crois que je me suis planté en parlant de C++, c'est plutôt du java, tu te doutes donc que je ne connais pas non plus et en plus, comme java gère lui-même la mémoire, je ne vais pas être avancé. Moi, je ne connais que le C.

Ah oui, désolé. Le code est en Java (c'est d'ailleur marqué juste avant la section code ).

(2) D'autre part, ton algorithme ne me semble pas récursif, cf ce que je disais :

Exact. En voici une version récursive, qui se rapproche plus de mon explication du post précédent... J'ai essayé de faire un code plus lisible (au détriment des perfs)

Code java :

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Permutations {
 
	// variable global: précalcul des factoriels
	static int[] factoriel = null;
 
	// genere la permutation numero #k
	public static void generate(int k, List<String> E, List<String> result) {
		int rank = E.size();
 
		// fin de recursion
		if (rank==0) return;
 
		// division euclidienne
		int quotient = k/factoriel[rank-1];
		int remainder = k % factoriel[rank-1];
 
		// retire un element "x" de l'ensemble E
		String x = E.remove(quotient);
 
		// ajoute cet element a la solution
		result.add( x );
 
		// appel recursif sur l'ensemble E\{x}
		generate(remainder, E, result);
	}
 
	public static void main(String[] args) {
 
		// l'ensemble de départ
		String[] list = new String[] {"A","B","C","D"};
 
		// n = longueur de l'ensemble
		int n = list.length;
 
		// pré-calcul des factoriel de 0 à n
		factoriel = new int[n+1];
		factoriel[0]=1;
		for(int i=1;i<=n;i++) factoriel[i]=i*factoriel[i-1];
 
		// nombre total de permutations = factoriel(n)
		int max=factoriel[n];
 
		// genere toutes les permutations
		for(int k=0;k<max;k++) {
			// copie de travail de la liste originale
			List<String> original = new ArrayList<String>(Arrays.asList(list));
 
			// intialise la liste qui contiendra le resultat 
			List<String> result = new ArrayList<String>();
 
			// construit la permutation #k 
			generate(k,original,result);
 
			// affiche la permutation
			System.out.println("Permutation #"+k+": "+result);
		}
	}
}

(3) Combien de temps CPU mets-tu pour passer en revue le cas n=12 ?

Sur mon vieux PC, la génération d'une seule permutation est de 0.0035 ms. Donc la génération de la totalité des 479001600 permutations doit faire dans les 30 minutes. Mais ce code est loin d'être optimisé pour les perfs et Java n'est pas connu pour sa vitesse ().

Le gros avantage de ces 2 implémentations c'est que la génération est parallelisable et ne consomme pas beaucoup de mémoire. Dans l'idéal, on pourrait répartir la génération des n! permutations sur n! PC et avoir le résultat instantanément.

La version récursive doit être extrêmement rapide avec un langage comme Haskell. Si Jedai lit ce post, il pourra sûrement le confirmer.