IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Permutation avec répétition


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 80
    Points : 75
    Points
    75
    Par défaut 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) ?

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par c-candide Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 80
    Points : 75
    Points
    75
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    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 Voir le message
    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 ?

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par c-candide Voir le message
    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);
    		}
    	}
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 80
    Points : 75
    Points
    75
    Par défaut
    Quand je disais

    Citation Envoyé par c-candide Voir le message
    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 Voir le message
    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 Voir le message
    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 ?

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par c-candide Voir le message
    (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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 80
    Points : 75
    Points
    75
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    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 Voir le message
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Comme tu demandais:
    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 Voir le message
    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.

    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.

    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


    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 ().
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 80
    Points : 75
    Points
    75
    Par défaut
    Citation Envoyé par pseudocode Voir le message

    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 Voir le message
    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.

  10. #10
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    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.


    Citation Envoyé par c-candide Voir le message
    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.
    ?

    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

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


    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 80
    Points : 75
    Points
    75
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    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)).

  12. #12
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    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.

    *) 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).

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

  13. #13
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par c-candide Voir le message
    *) 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 ?
    Oups. Effectivement il n'y a qu'un seul "p". Generalement je dis "Tuple" mais je voulais rester francophone.... ca m'apprendra.

    *) 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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]

    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)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #14
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    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
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  15. #15
    Membre averti

    Profil pro
    Étudiant
    Inscrit en
    Décembre 2004
    Messages
    499
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2004
    Messages : 499
    Points : 422
    Points
    422
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  16. #16
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    @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).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  17. #17
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 80
    Points : 75
    Points
    75
    Par défaut
    Citation Envoyé par PRomu@ld Voir le message
    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 Voir le message
    Tu chipotes pour pas grand chose.
    Et encore t'as rien vu

    Citation Envoyé par PRomu@ld Voir le message
    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 Voir le message
    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 Voir le message
    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 Voir le message

    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 Voir le message
    après je vois aussi une version itérative (moins rapide ?)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 Voir le message
    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.

  18. #18
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par c-candide Voir le message
    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.

    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 .

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

    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
     
    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));
     
    	}
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  19. #19
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    @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é

    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.
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  20. #20
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Nemerle Voir le message
    1ièrement, c'est le diamond lemma de Bergman, laisse Paul de coté
    Bergman, comme le cinéaste ? T'es sûr... ?


    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. Enfin si j'ai bien compris...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Réponses: 14
    Dernier message: 16/08/2014, 20h05
  2. Réponses: 5
    Dernier message: 17/01/2013, 12h32
  3. Permutation avec une fonction récursive
    Par nypahe dans le forum Débuter avec Java
    Réponses: 1
    Dernier message: 29/04/2009, 08h32
  4. Permutation sans répétition
    Par vincent_LSCP dans le forum MATLAB
    Réponses: 4
    Dernier message: 13/01/2009, 20h21
  5. combinatoire avec répétitions
    Par xenozephyr dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 27/03/2008, 22h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo