Permutation avec répétition

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) ?

Citation:

---

Envoyé par c-candide

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.

Citation:

---

Envoyé par pseudocode

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.

Citation:

---

Envoyé par pseudocode

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 ?

Citation:

---

Envoyé par c-candide

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:

---

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:

---

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); } } }

---

Quand je disais

Citation:

---

Envoyé par c-candide

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

Citation:

---

Envoyé par pseudocode

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 :

Citation:

---

Envoyé par c-candide

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 ?

Citation:

---

Envoyé par c-candide

(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 ;)).

Citation:

---

(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:

---

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); } } }

---

Citation:

---

(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 (:aie:).

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.

Citation:

---

Envoyé par pseudocode

Exact. En voici une version récursive,

---

En fait la récursivité est très marginale ici (elle concerne juste la détermination de la k-ième permutation), mais l'implémentation reste fondamentalement itérative, précisément à cause de cela :

Citation:

---

Envoyé par pseudocode

Code:

---

1 2 3 4 5 6 7 8 9

// nombre total de permutations = factoriel(n) int max=factoriel[n];   // genere toutes les permutations for(int k=0;k<max;k++) { /* on écrit la permutation correspondant au "classement" */   }

---

---

C'est une variante certes moins naturelle mais assez astucieuse de la traditionnelle génération utilisant l'ordre lexicographique (partant d'une permutation, on recherche la suivante dans l'ordre lexicographique). Sinon, les objections de mon précédent message demeurent (je parlais d'un algorithme différent au départ).

Ton code me donne aussi une première occasion de lire du java dans le texte et je trouve ça très très lisible (ça doit aussi tenir à tes qualités de rédaction ;) ), s'il fallait faire les mêmes choses en C, ce serait bien plus compliqué me semble-t-il. Si j'ai le temps, je tâcherai de l'écrire en C.

Comme tu demandais:

Citation:

---

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) ?

---

j'ai supposé qu'une version ne necessitant de mémoriser aucune des permutations précédantes suffirait a ton bonheur. ;)

Citation:

---

Envoyé par c-candide

En fait la récursivité est très marginale ici (elle concerne juste la détermination de la k-ième permutation), mais l'implémentation reste fondamentalement itérative, précisément à cause de cela :

---

Certe. C'est parceque j'ai chosi de construire un fonction "P(n)={Liste}" qui me permet de calculer n'importe quelle permutation. Visiblement tu préfererais une fonction "next( {Liste1} ) = {Liste2}" qui calcule une permutation à partir d'une autre. C'est possible de faire cela avec ma version car la fonction est inversible: "next( {Liste1} ) = P ( Pinverse({Liste1}) + 1 )". Je n'en vois pas trop l'interet, mais ca reste possible.

Citation:

---

Sinon, les objections de mon précédent message demeurent (je parlais d'un algorithme différent au départ).

---

Hum... D'après ce que j'ai compris tu parlais de générer les solutions en utilisant les operateurs de transposition. Mais j'ai pas bien vu le rapport avec la recursion car le calcul de la "prochaine" transposition est itératif. :koi:

Transposition = n-upplet {a1,..,ai,..,an} avec 1<=ai<=i

Et dans le cas des permutations avec répetitions, si les element "i" et "k" sont identiques (k<i) alors c'est ak<ai<=i

Par exemple pour {"P","P","A","A"}, on obtient 6 n-upplets possibles:

1<=a1<=1, a1<a2<=2, 1<=a3<=3, a3<a4<=4

{1, 2, 1, 2} -> A A P P
{1, 2, 1, 3} -> A P A P
{1, 2, 1, 4} -> A P P A
{1, 2, 2, 3} -> P A A P
{1, 2, 2, 4} -> P A P A
{1, 2, 3, 4} -> P P A A

Citation:

---

Ton code me donne aussi une première occasion de lire du java dans le texte et je trouve ça très très lisible (ça doit aussi tenir à tes qualités de rédaction ;) ), s'il fallait faire les mêmes choses en C, ce serait bien plus compliqué me semble-t-il. Si j'ai le temps, je tâcherai de l'écrire en C.

---

La principale difficulté va etre de porter les classes qui gerent les listes. D'un autre coté ca permettra d'augmenter les perfs car ces classes ne sont pas spécialement rapides (:aie:).

Citation:

---

Envoyé par pseudocode

Hum... D'après ce que j'ai compris tu parlais de générer les solutions en utilisant les operateurs de transposition.

---

Pas exactement, ce que j'ai dit c'est que l'usage des transpositions (échange de deux éléments) semble poser le même problème que pour l'algorithme d'insertion. Je précise à nouveau que l'idée de cet algorithme est une récursion. Mais les deux méthodes présentent l'inconvénient selon moi qu'une étape typique de l'algorithme semble nécessiter la connaissance de toutes les permutations pour un item de moins. Je détaille dans la cas de l'insertion :

Je veux la liste de toutes les permutations de trois éléments A, B et C :
Étape récursive : j'appelle ma liste de permutations sur les 2 éléments B et C :
a) BC
b) CB
La permutation a) engendre par "insertion" de A les trois permutations suivantes :
ABC, BAC et BCA.
La permutation b) engendre par "insertion" de A les trois permutations suivantes :
ACB, CAB et CBA

ce qui au total donne les 6 permutations de A, B et C.

Je m'intéresse à cette méthode parce que c'est celle qui me parait la plus naturelle avec la méthode que j'évoque à la fin de ce message. Il est facile d'implémenter un algorithme qui suive exactement cette récursion : il suffit pour cela de stocker la liste de toutes les permutations pour le rang n (un malloc échouera rapidement sauf à coder avec des bits mais bonjour la galère, donc il faudra stocker dans un fichier -> lent), d'en déduire par l'algorithme détaillé ci-dessus sur un exemple la liste des permutations sur n+1 objets, permutations qu'il faudra a priori à nouveau mémoriser tandis qu'on pourra libérer l'espace occupé par les permutations sur n objets.

Maintenant, je repose ma question : je me demandais s'il existait une astuce quelconque qui utiliserait le même algorithme (donc récursif de la même façon) et qui pourrait se dispenser de stocker toutes les permutations. Personnellement, je suis parvenu à le faire par une méthode (dont je pourrais poster une implémentation en C) différente de la tienne mais basée sur la même idée, à savoir je place A en première position et je lui colle toutes les permutations sur B et C, puis je place en 1ère position B etc.) Dans mon implémentation j'arrive à coller par exemple à A les permutations de B et C sans les avoir mémorisées et je me disais qu'on doit pouvoir faire pareil pour la méthode d'insertion.

Voilà, désolé d'avoir été aussi verbeux et redondant et si maintenant ma question n'est pas comprise, ce sera sans espoir.

Citation:

---

Envoyé par pseudocode

Par exemple pour {"P","P","A","A"}, on obtient 6 n-upplets possibles:

1<=a1<=1, a1<a2<=2, 1<=a3<=3, a3<a4<=4

{1, 2, 1, 2} -> A A P P
{1, 2, 1, 3} -> A P A P
{1, 2, 1, 4} -> A P P A
{1, 2, 2, 3} -> P A A P
{1, 2, 2, 4} -> P A P A
{1, 2, 3, 4} -> P P A A

---

OK, ce n'est pas récursif mais c'est assez joli et ça mériterait d'être regardé de plus près. Dans le principe ça paraît simple ça veut pas dire pour autant que l'implémentation ne réservera pas des surprises.

En fait pour les anagrammes en itératif, c'est encore la méthode de l'ordre lexicographique qui me parait la plus simple, l'idée étant qu'on code une fonction Suivant qui étant, donné un alphabet, fournit le mot suivant (s'il existe) d'un mot donné en entrée. Après il n'y a plus qu'à lancer la fonction Suivant sur le premier mot que l'on peut construire sur l'alphabet donné et à arrêter quand le mot courant n'a pas de suivant.

Citation:

---

Voilà, désolé d'avoir été aussi verbeux et redondant et si maintenant ma question n'est pas comprise, ce sera sans espoir.

---

bon, je suis un cas désespéré alors. :aie:

Citation:

---

Envoyé par c-candide

Je précise à nouveau que l'idée de cet algorithme est une récursion. Mais les deux méthodes présentent l'inconvénient selon moi qu'une étape typique de l'algorithme semble nécessiter la connaissance de toutes les permutations pour un item de moins.

---

:koi: ?

Pour connaitre TOUTES les permutations de rang "n", il faut connaitre TOUTES les permutations de rang "n-1"

Pour connaitre UNE permutation de rang "n", il suffit de connaitre UNE permutation de rang "n-1" et d'appliquer la formule de recurence.

Pour connaitre X permutations de rang "n", il faut connaitre Y permutations de rang "n-1". La relation entre les nombres X et Y dépend de la formule de recursion

Citation:

---

Maintenant, je repose ma question : je me demandais s'il existait une astuce quelconque qui utiliserait le même algorithme (donc récursif de la même façon) et qui pourrait se dispenser de stocker toutes les permutations.

---

heu... oui. En repartant de la formule des transpositions:

Transposition = n-upplet {a1,..,ai,..,an} avec 1<=ai<=i

il suffit de calculer "an" en fonctions des a1,...,a(n-1). On peut meme y ajouter un test pour gerer les répetitions:

Code:

---

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 64 65 66 67

import java.util.ArrayList; import java.util.Arrays; import java.util.List;   public class PermutationWithRepetition {   static String[] list;   // genere la sequence associée a la transposition public static List<String> transposition(int[] nupplet) { List<String> result = new ArrayList<String>(); for(int i=0;i<nupplet.length;i++) { result.add(nupplet[i], list[i]); } return result; }   // 1ere transposition valide (contrainte sur les répetitions) public static void initnuplet(int[] nupplet) { nupplet[0]=0; for(int i=1;i<nupplet.length;i++) { if (list[i].equals(list[i-1])) nupplet[i]=nupplet[i-1]+1; else nupplet[0]=0; } }   // calcule la prochaine transposition, par recursion public static boolean nextnuplet(int[] nupplet, int pos) { // fin de recursion if (pos<0) return false;   // a(i)<i --> on peut incrementer ai if (nupplet[pos]<pos) {nupplet[pos]++; return true;}   // sinon on calcule a(i-1) if (!nextnuplet(nupplet,pos-1)) return false;   // et on initialise a(i) = 0 ou a(i)+1 suivant les repetitions if ( (pos>0) && (list[pos].equals(list[pos-1])) ) nupplet[pos]=nupplet[pos-1]+1; else nupplet[pos]=0;   return true; }   public static void main(String[] args) {   // l'ensemble de départ list = new String[]{"P","P","A","A"};   // n = longueur de l'ensemble int n = list.length;   // transposition initiale int[] nupplet = new int[n]; initnuplet(nupplet);   // affiche la liste initiale System.out.println(Arrays.toString(nupplet)+": "+transposition(nupplet));   // affiche toutes les transpositions while(nextnuplet(nupplet,n-1)) { System.out.println(Arrays.toString(nupplet)+" -> "+transposition(nupplet)); }   } }

---

Citation:

---

OK, ce n'est pas récursif mais c'est assez joli et ça mériterait d'être regardé de plus près. Dans le principe ça paraît simple ça veut pas dire pour autant que l'implémentation ne réservera pas des surprises.

---

Si tu t'imposes le recursif, c'est sur que ca ne va pas faciliter l'implémentation dans un langage impératif. :P

Citation:

---

Envoyé par pseudocode

heu... oui. En repartant de la formule des transpositions:

Transposition = n-upplet {a1,..,ai,..,an} avec 1<=ai<=i

---

Je comprends pas tes notations :

*) pourquoi écris-tu n-upplet avec deux p, c'est pas les mêmes "n-uplets" que d'habitude, cf. http://fr.wikipedia.org/wiki/N-uplet ?
*) ai<=i, je suppose que ça veut dire a[i]<=i, mais je croyais que tu travaillais avec des chaînes de caractères (genre PAPA) donc visiblement le n-uplet ne sera pas constitué de caractères, alors de quoi est-il constitué par rapport à la chaîne dont on cherche à lister les permutations ?
*) surtout, pourquoi tu appelles un n-uplet une transposition ? une transposition c'est une permutation particulière (elle échange deux valeurs et laisse fixe les autres, dans ton cas, je ne vois pas les deux valeurs censées être échangées), cf. par exemple le wiki transposition
*) Qu'est ce que tu appelles la formule des transpositions (quelle formule ? pour moi une formule, c'est une égalité genre la formule du binôme de Newton) ?

Bon j'ai l'impression qu'on ne parle pas la même langue (ni le même langage d'ailleurs, je crois que le pseudo-code plutôt que C ou java mettrait tout le monde d'accord)).

Citation:

---

pourquoi écris-tu n-upplet avec deux p, c'est pas les mêmes "n-uplets" que d'habitude,

---

C'est une faute de français, ça ne vaut pas le coup de polémiquer là dessus ... . Tu chipotes pour pas grand chose.

Citation:

---

*) ai<=i, je suppose que ça veut dire a[i]<=i, mais je croyais que tu travaillais avec des chaînes de caractères (genre PAPA) donc visiblement le n-uplet ne sera pas constitué de caractères, alors de quoi est-il constitué par rapport à la chaîne dont on cherche à lister les permutations ?

---

Tu peux assimiler les caractères à des nombres entiers (l'ensemble des caractères est dénombrable).

Citation:

---

je crois que le pseudo-code plutôt que C ou java mettrait tout le monde d'accord)

---

Oui, bien évidement ;)

Citation:

---

Envoyé par c-candide

*) pourquoi écris-tu n-upplet avec deux p, c'est pas les mêmes "n-uplets" que d'habitude, cf. http://fr.wikipedia.org/wiki/N-uplet ?

---

:oops: Oups. Effectivement il n'y a qu'un seul "p". Generalement je dis "Tuple" mais je voulais rester francophone.... ca m'apprendra.

Citation:

---

*) ai<=i, je suppose que ça veut dire a[i]<=i, mais je croyais que tu travaillais avec des chaînes de caractères (genre PAPA) donc visiblement le n-uplet ne sera pas constitué de caractères, alors de quoi est-il constitué par rapport à la chaîne dont on cherche à lister les permutations ?*) surtout, pourquoi tu appelles un n-uplet une transposition ? une transposition c'est une permutation particulière (elle échange deux valeurs et laisse fixe les autres, dans ton cas, je ne vois pas les deux valeurs censées être échangées), cf. par exemple le wiki transposition
*) Qu'est ce que tu appelles la formule des transpositions (quelle formule ? pour moi une formule, c'est une égalité genre la formule du binôme de Newton) ?

---

Non le n-uplet (;)) n'est pas composé de caracteres mais de nombres.

Pour faire simple, on peut dire que l'element "k" du n-uplet représente la position d'insertion du "k"-ième element.

Par exemple: E={A,B,C} et Transposition={1,2,1}

{1,2,1} --> insertion de "A" en position 1 --> {A}
{1,2,1} --> insertion de "B" en position 2 --> {AB}
{1,2,1} --> insertion de "C" en position 1 --> {CAB}

C'est peut-etre plus simple a voir a partir des permutations:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

E={A,B,C}   A {1} ______|______ | | BA {1,1} AB {1,2} | | CBA {1,1,1} CAB {1,2,1} BCA {1,1,2} ACB {1,2,2} BAC {1,1,3} ABC {1,2,3}

---

On peut donc associer une permutation avec l'écriture d'un n-uplet. (c'est ce que j'appellais la "formule" de transposition, quoiqu'il est vrai que le mot formule est mal employé et qu'il vaut mieux parler de "notation").

Cette ecriture est tres pratique car, par définition, la valeur du k-ième element du n-uplet est toujours entre 1 et k. Et en cas de répétition, il suffit de maintenir une relation d'ordre sur la valeur des elements du n-uplet associés aux répetitions (par exemple "strictement superieur")

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

E={A,P,P} A {1} ______|______ | | PA {1,1} AP {1,2} | | PPA {1,1,1} PAP {1,2,1} PPA {1,1,2} APP {1,2,2} PAP {1,1,3} APP {1,2,3} Les permutations en bleu ne sont pas valides car il faut que a[3]>a[2]

---

Citation:

---

Bon j'ai l'impression qu'on ne parle pas la même langue (ni le même langage d'ailleurs, je crois que le pseudo-code plutôt que C ou java mettrait tout le monde d'accord)).

---

Les algos en eux meme sont assez simples. C'est plus un probleme de signification de la structure de données (le n-uplet)

Petite remarque: la transposition (1,2) et le cycle (1,2,...,n) génèrent tout le groupe symétrique Sn...

Add-on: il me revient aussi un algo performant: il suffit d'appliquer le diamond lemna sur les transpositions t(i)=(i,i+1), avec les relations

t(i)^2=1, t(i)t(j)=t(j)t(i) si |j-i|>1 et [t(i)t(i+1)]^3=1

Bonjour

je n'ai pas bien compris: pourquoi ne pas utiliser des combinaisons ?

on a {a_1,a_2,...a_n} : a_i est le nombre de fois qu'apparait le lettre i dans le mot

en tout il y a N lettres: a_1 + a_2 ... + a_n = N
pour générer une des permutations:
on choisit les places des a_1 lettres 1 (parmis N)
ensuite on choisit les places des a_2 lettres 2 (parmis N-a_1)
...
il reste a_n places pour les lettres n

___________________

après je vois aussi une version itérative (moins rapide ?)

Code:

---

1 2 3 4 5 6 7 8

permutation_suivante (tableau t) { i := taille(t) tant que t[i] < t[i-1] i := i - 1 fin tant que echanger(t[i],t[i-1]) inverser la partie de t située à partir de la case i }

---

exemple:
00123210
on décrémente tant que t[i] < t[i-1]
donc on se retrouve entre le 2 et le 3:
0012.3210
on échange le 2 et le 3:
0013.2210
puis on inverse l'ordre de la partie située à partir de la case i:
00130122

Renaud

@Nemerle: je ne vois pas bien comment utiliser le diamand de Newman pour construire un itérateur... Tu as un exemple ?

@acx01b: oui, il y avais plus simple pour trouver des anagrammes. Mais le PO voulait une solution a base de transposition avec une complexité mémoire en o(n).

Citation:

---

Envoyé par PRomu@ld

C'est une faute de français, ça ne vaut pas le coup de polémiquer là dessus ... . Tu chipotes pour pas grand chose.

---

Je ne tire jamais le premier. C'est toi qui ne remets pas les choses dans leur contexte : s'il n'y avait eu que cela, j'aurais compris qu'il s'agissait d'une coquille ou d'un lapsus. Mais, il avait de nombreuses autres ambigüités ("transposition", "formule") qui fait qu'on a besoin de vocabulaire précis. Par ailleurs, un algorithme, c'est un certain dosage entre concept et "chipotage".

Citation:

---

Envoyé par PRomu@ld

Tu chipotes pour pas grand chose.

---

Et encore t'as rien vu ;)

Citation:

---

Envoyé par PRomu@ld

Tu peux assimiler les caractères à des nombres entiers (l'ensemble des caractères est dénombrable).

---

Je le sais bien mais visiblement ce que tu dis ne correspond pas à ce que disait pseudocode : la suite a[i] est constitué d'indices de caractères.
Quand à l'ensemble des caractères, il est certes dénombrable (je suppose que tu parles au sens mathématiques du terme) mais il est surtout fini donc je ne vois pas ce que ta remarque apporte.

Citation:

---

Envoyé par pseudocode

:oops: Oups. Effectivement il n'y a qu'un seul "p".

---

Ce n'est pas grave du tout mais ce qui m'a vraiment gêné c'est l'emploi du terme transposition totalement inapproprié vu le sens courant du terme d'autant plus qu'il existe des méthodes de génération des permutations qui utilisent des "vraies" transpositions (le terme insertion aurait été mieux) ainsi que le terme de formule (le terme de codage était plus adapté un peu comme on parle du codage de Prufer d'un arbre).

Bon, j'ai très bien compris ton codage, il est clair qu'il y a une bijection entre l'ensemble des n-uplets (a_1,...,a_n) de {1,...,n} tels que pour tout indice k, on ait a_k <= k et l'ensemble des permutations de {1,...,n}. Maintenant, je vais prendre le temps de regarder ton algorithme en java pour savoir s'ilrésout mon problème d'allocation.

En tous cas, merci de ta patience et du soin que tu as apporté à ta dernière réponse.

Citation:

---

Envoyé par Nemerle

Petite remarque: la transposition (1,2) et le cycle (1,2,...,n) génèrent tout le groupe symétrique Sn...

---

Certes mais ça reste un résultat théorique, comment tu vas savoir que tu as toutes
les permutations (faut gérer le nombre de permutations déjà construites et donc gérer les répétitions et donc a priori, il faut mémoriser toutes les permutations déjà acquises) ?

Et en outre, tu peux avoir une composition très compliquée de la transposition et du n-cycle pour obtenir une certaine permutation.

Citation:

---

Envoyé par acx01b

en tout il y a N lettres: a_1 + a_2 ... + a_n = N
pour générer une des permutations:
on choisit les places des a_1 lettres 1 (parmis N)
ensuite on choisit les places des a_2 lettres 2 (parmis N-a_1)
...
il reste a_n places pour les lettres n

---

ça c'est une première méthode qui explique d'ailleurs que le nombre d'anagrammes est un coefficient multinomial

Citation:

---

Envoyé par acx01b

après je vois aussi une version itérative (moins rapide ?)

Code:

---

1 2 3 4 5 6 7 8

permutation_suivante (tableau t) { i := taille(t) tant que t[i] < t[i-1] i := i - 1 fin tant que echanger(t[i],t[i-1]) inverser la partie de t située à partir de la case i }

---

exemple:
00123210
on décrémente tant que t[i] < t[i-1]
donc on se retrouve entre le 2 et le 3:
0012.3210
on échange le 2 et le 3:
0013.2210
puis on inverse l'ordre de la partie située à partir de la case i:
00130122

---

et ça c'est une deuxième méthode qui correspond à la méthode de l'ordre lexicographique dont j'ai parlée : le mot 00130122 est le successeur immédiat de 00123210 pour l'alphabet {0,1,2,3}

Citation:

---

Envoyé par pseudocode

Mais le PO voulait une solution a base de transposition avec une complexité mémoire en o(n).

---

Désolé de revenir là-dessus mais pas "transposition" mais "insertion". Pour la mémoire, s'il c'est polynomial, par exemple O(n^2), ça convient aussi.

Citation:

---

Envoyé par c-candide

Ce n'est pas grave du tout mais ce qui m'a vraiment gêné c'est l'emploi du terme transposition totalement inapproprié vu le sens courant du terme d'autant plus qu'il existe des méthodes de génération des permutations qui utilisent des "vraies" transpositions

---

Ahhhhh.... je viens de capter en lisant l'article le wikipedia: "Transposition = Échange de 2 éléments". Arf. Je comprend mieux d'où venait l'embrouille.

Dans mon post, je parlais de "Transposition" au sens matriciel, comme une fonction qui effectue une permutation d'un ensemble fini.

Citation:

---

Bon, j'ai très bien compris ton codage, il est clair qu'il y a une bijection entre l'ensemble des n-uplets (a_1,...,a_n) de {1,...,n} tels que pour tout indice k, on ait a_k <= k et l'ensemble des permutations de {1,...,n}. Maintenant, je vais prendre le temps de regarder ton algorithme en java pour savoir s'ilrésout mon problème d'allocation.

---

Dans cet algo, il n'y a pas d'allocation autre que le n-uplet (donc en o(n)).

A noter que mon code est loin d'être joli, surtout le calcul récursif du prochain n-uplet :aie:.

Ça serait plus simple si on pouvait générer le code itératif spécifique a l'ensemble de départ:

Code:

---

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

import java.util.ArrayList; import java.util.Arrays; import java.util.List;   public class PermutationWithRepetition {   static String[] list;   // genere la sequence associée au nuplet public static List<String> generate(int[] nuplet) { List<String> result = new ArrayList<String>(); for (int k = 0; k < nuplet.length; k++) { // insere le k-ieme element a la position // spécifiée par le kieme n-uplet result.add(nuplet[k], list[k]); } return result; }   public static void main(String[] args) {   // l'ensemble de départ list = new String[] { "P", "P", "A", "A" };   // n = longueur de l'ensemble int n = list.length;   // n-uplet initial int[] nuplet = new int[n];   // boucle sur toutes les valeurs permises du n-uplet for(nuplet[0]=0; nuplet[0]<=0; nuplet[0]++)   for(nuplet[1]=nuplet[0]+1; nuplet[1]<=1; nuplet[1]++)   for(nuplet[2]=0; nuplet[2]<=2; nuplet[2]++)   for(nuplet[3]=nuplet[2]+1; nuplet[3]<=3; nuplet[3]++)   System.out.println(Arrays.toString(nuplet)+" -> "+generate(nuplet));   } }

---

Citation:

---

Envoyé par pseudocode

@Nemerle: je ne vois pas bien comment utiliser le diamand de Newman pour construire un itérateur... Tu as un exemple ?

---

1ièrement, c'est le diamond lemma de Bergman, laisse Paul de coté :mouarf:

Une façon de voir les choses ici: on recherche une base (monomiale) de l'espace vectorielle R<t_1,...,t_n> / I où I est l'idéal engendré par les 3 relations donnés plus haut entre les ti (t_i^2=1, etc).

Avec un ordre et des règles de réduction, tu peux donc appliquer le diamond pour obtenir ta base (Gröbner non commutatif, ça te dit?); je crois que la version algo du diamond est l'algo de Buchberger.

M'enfin, ça remonte à loin, mais à l'époque où je travaillais sur ce style d'algèbres (au niveau des groupes quantiques), on laissait l'ordi nous donner des bases avec cette méthode.

Citation:

---

Envoyé par Nemerle

1ièrement, c'est le diamond lemma de Bergman, laisse Paul de coté :mouarf:

---

Bergman, comme le cinéaste ? T'es sûr... ? :aie:

Citation:

---

Avec un ordre et des règles de réduction, tu peux donc appliquer le diamond pour obtenir ta base (Gröbner non commutatif, ça te dit?); je crois que la version algo du diamond est l'algo de Buchberger.

---

Ca revient un peu a faire mon premier algo (avec des divisions euclidiennes successives) pour trouver le n-uplet représentant une permutation.

Bien sur, la c'est beaucoup plus rigoureux car le n-uplet est une coordonnée dans une base. 8-) Enfin si j'ai bien compris... :roll:

Citation:

---

Envoyé par pseudocode

Bien sur, la c'est beaucoup plus rigoureux car le n-uplet est une coordonnée dans une base. 8-) Enfin si j'ai bien compris... :roll:

---

Oui. Prends le cas du groupe quantique Uq(sl2C) où q est un complexe <>0 et 1: c'est le quotient de la C-algèbre libre L de générateur x,y,k et k^(-1) par l'idéal I engendré par les relations
kk^(-1)=k^(-1)k=1
kx=(q^2)xk
yk=(q^2)ky
(q-q^(-1)).(xy-yx)=k-k^(-1).

Comment, pour pouvoir tafer, trouver une C-base de Uq(sl2C) =L/I ? Via le diamond lemma et son algo!! Et avec un bon ordre et tes règles de réduction, tu montres qu'une telle base, c'est les x^a.y^b.k^c où a,b,c sont des entiers...

http://xray.club.fr/dvpimg/knockout.jpg

(visiblement on n'a pas le même niveau en algebre)

Citation:

---

Envoyé par pseudocode

Dans cet algo, il n'y a pas d'allocation autre que le n-uplet (donc en o(n)).

---

OK, je viens de regarder ton implémentation oui, c'est en O(n) mais à nouveau la récursivité est marginale voire factice comme tu l'expliques toi-même, elle sert juste à calculer l'élément suivant dans l'ordre lexicographique mais sinon, on parcourt les permutations de la première à la dernière (certes via ce que moi j'appele leur "codage") :

Citation:

---

Envoyé par pseudocode

Code:

---

1 2 3 4

// affiche toutes les transpositions while(nextnuplet(nupplet,n-1)) { System.out.println(Arrays.toString(nupplet)+" -> "+transposition(nupplet));

---

---

d'où le côté vraiment itératif de l'algorithme. Il n'empêche que ton codage est tout à fait intéressant et original et tu n'as pas codé en vain.

Je précise que j'insiste sur l'aspect récursif car ce message trouve son origine dans un fil de discussions sur un autre site où le jeu consistait à lister des problèmes à résoudre vraiment récursivement et j'avais proposé la génération des anagrammes.

Je vais reprendre le code C de l'algorithme récursif que j'avais écrit et qui est basé sur un algorithme différent (détaillé par pseudocode dans une de ses réponses) et le transformer en pseudo-code et je le posterai dès que je peux, ça donnera peut-être une idée à quelqu'un pour la méthode d'insertion. Merci de vos interventions, en particulier à pseudocode.

Ah... c'etait un defi. Dans ce cas tu aurais du le poster dans le forum d'à coté. Ils auraient surement été meilleurs que moi.

Citation:

---

Je vais reprendre le code C de l'algorithme récursif que j'avais écrit et qui est basé sur un algorithme différent (détaillé par pseudocode dans une de ses réponses) et le transformer en pseudo-code et je le posterai dès que je peux, ça donnera peut-être une idée à quelqu'un pour la méthode d'insertion. Merci de vos interventions, en particulier à pseudocode.

---

:king:

Citation:

---

Envoyé par pseudocode

Ah... c'etait un defi. Dans ce cas tu aurais du le poster dans le forum d'à coté

---

C'est vrai que j'aime bien ce genre de défi, je le saurai pour une autre fois, pour l'instant je manque pas mal de temps. A+.

Citation:

---

Envoyé par c-candide

Je vais reprendre le code C de l'algorithme récursif que j'avais écrit et qui est basé sur un algorithme différent (détaillé par pseudocode dans une de ses réponses) et le transformer en pseudo-code et je le posterai dès que je peux

---

Présentation rapide et exemple
Soit f(resultat[1..n], mot[taille]) une procédure qui affiche tous les anagrammes
de la chaîne mot[taille] (dans le pseudo-code ci-dessous, f s'appellera anagramme_rec)
L'algorithme est immédiatement récursif, c'est-à-dire qu'il lance la procédure
récursive immédiatement et non pas au sein d'une boucle principale (à la différence des algos déjà donnés dans ce fil).

Description de l'étape récursive
L'étape récursive est constituée d'une boucle qui parcourt chacune des lettres
distinctes de la chaine mot[taille], qui place la lettre courante en tête du tableau
résultat et qui,
si taille >1, échange les positions debut de mot avec lettre courante et rappelle la fonction f sur resultat[2..n] et mot[taille -1]
et sinon affiche resultat[1..n].

Illustration avec mot[taille]=PAPAS .

f(resultat[1..5]=?????,PAPAS)
/* PAPAS a trois lettres "distinctes" : P, A, S
il y aura donc trois appels récursifs. */

1ere lettre "distincte" P :
resultat[1..5]=P????;
f(resultat[2..5]=????,APAS);/* 1er appel récursif */

2ème lettre "distincte" A :
resultat[1..5]=A????;
f(resultat[2..5]=????,PPAS);/* 2eme appel récursif */

3ème lettre "distincte" S :
resultat[1..5]=S????;
f(resultat[2..5]=????,APAP);/* 3eme appel récursif */

Détails à régler
Entre autres :

-- il faut sauver le contenu de mot en début de boucle pour pouvoir retrouver
les différentes lettres. On peut supprimer la sauvegarde en fin de boucle.
-- il faut gérer la répétition des lettres pour extraire les lettres distinctes.


Pseudo-code

Code:

---

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

Procédure anagramme_rec(resultat[1..n], mot[taille]) Création d'un tableau char copie_mot[taille]; /* on sauvegarde le mot courant dans copie */ Pour (i = 1.. taille) copie_mot[i] = mot[i]; /* on parcourt les lettres distintes de mot[taille] */ Si (taille > 1) /* cas du mot ayant au moins deux lettres */ Création d'un tableau bool deja_servi[taille]={0};   Pour (j = 1..taille) /* on extrait que les lettres qui n'ont pas déjà été utilisées */ si (deja_servi[j] = NON)   Pour (k = 1..taille) /* gestion de la répétition de lettres */ Si (copie_mot[k] = copie_mot[j]) alors deja_servi[k] = 1; k++; Fin pour   /* on remplit resultat de la lettre courante */ resultat[n - taille] = copie_mot[j];   /*mise a jour du mot courant */ Pour (i = 1..taille) mot[i] = copie_mot[i]; i++; Fin Pour   /* on échange la tête de mot avec la lettre courante : */ mot[j] = copie_mot[1]; mot[1] = resultat[n - taille]; /* L'appel recursif */ anagramme_rec(resultat, mot + 1, taille - 1, n); fin si j++; fin pour Libération de l'espace-mémoire du tableau deja_servi;   sinon resultat[n - 1] = copie_mot[1]; afficher(resultat[1..n]); fin sinon Libération de l'espace-mémoire du tableau copie_mot; fin si Fin procedure anagramme_rec;     N=taille de mot anagramme_rec(resultat[1..N], mot[1..N]);

---

La complexité en espace mémoire
C'est un O(N^2) où N est la taille du mot initial : il y a jusqu'à N-1 appels recursifs imbriqués et chaque appel consomme deux tableaux de taille taille et taille diminue d'une unité à chaque étape. Chaque espace est libéré en fin de boucle.

Compilation, exécution et affichage, code source en C

Code:

---

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

candide@candide-desktop:~$ gcc -W -Wall -pedantic -o x anagrammes_rec.c candide@candide-desktop:~$ ./x papas papsa paaps paasp pasap paspa ppaas ppasa ppsaa pspaa psapa psaap appas appsa apaps apasp apsap apspa aapps aapsp aaspp aspap asppa asapp sapap sappa saapp spaap spapa sppaa candide@candide-desktop:~$

---

Ci-dessous, les retours d'alloc ne sont pas testés, je sais c'est mal.

Code:

---

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 64 65 66 67

#include <stdio.h> #include <stdlib.h> #include <string.h>   void anagramme(char *resultat, char *mot, int taille, int n) { char *copie_mot = malloc(taille);   { int i;   for (i = 0; i < taille; i++) copie_mot[i] = mot[i]; } if (taille > 1) { int j, k; int *deja_servi = calloc(taille, sizeof(int));   for (j = 0; j < taille; j++) { if (deja_servi[j] == 0) { for (k = 0; k < taille; k++) { if (copie_mot[k] == copie_mot[j]) deja_servi[k] = 1; } resultat[n - taille] = copie_mot[j]; { int i;   for (i = 0; i < taille; i++) mot[i] = copie_mot[i];   } mot[j] = copie_mot[0]; mot[0] = resultat[n - taille];   anagramme(resultat, mot + 1, taille - 1, n); } } free(deja_servi); } else { int i;   resultat[n - 1] = copie_mot[0]; for (i = 0; i < n; i++) printf("%c", resultat[i]); printf("\n"); } free(copie_mot); }   int main(void) { char mot[] = "papas"; size_t N = strlen(mot); char *resultat = malloc(N);   anagramme(resultat, mot, N, N); free(resultat); return 0; }

---

Commentaires sur l'algorithme, le code C, des prolongements possibles sont les bienvenus même si je vais être peut être moins disponible dans les jours à venir.