Discussion :

[Nemerle]

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

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

[pseudocode]

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

[c-candide]

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") :

Code java :

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

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.

[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.

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.

[c-candide]

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+.

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

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

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

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
 
#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.