Discussion :

[millie]

Comme j'ai vu pas mal de fois le problème de la détermination des combinaisons de n chiffres ou de n caractères par exemple, je propose un ajout sur ça.


On va donner un algorithme qui va permettre de donner les combinaisons de n caractères d'une liste de symbole (par exemple 0 à 9 ou c à f). Comme justement ces symboles peuvent être particuliers, on peut définir un Type et leur attribuer 3 fonctions.

- init() qui retourne le plus petit symbole (par exemple 0 pour les chiffres)
- suivant(Type t) retourne le symbole suivant (par exemple suivant(0) = 1 ou suivant(b) = c)
- estALaLimite(Type t) qui retourne vrai si le symbole est à la limite des symboles que l'on souhaite (par exemple 9 pour les chiffres de 0 à 9, ou g pour les caractères de b à g.

On considère un tableau de taille n d'un certain Type, et on va déterminer toutes les combinaisons possibles de n caractères en les inscrivant dans ce tableau.

Une manière de faire et d'imaginer que l'on a affaire à une recherche de combinaisons de chiffre (par exemple les combinaisons de 4 caractères utilisant les chiffres de 0 à 9). On voit bien que pour passer q'une combinaison (par exemple 1239) à l'autre, on peut ajouter 1 (1240). On va utiliser ce principe pour générer toutes les combinaisons en effectuant une retenue si nécessaire.

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
 
/* T correspond au tableau et k à la position de la retenue*/
Procédure evoluerRetenue(Permutation T, Entier k)
  T[k] <- init()
  Si estALaLimite(T[k+1])
      Si k+1>n alors 
          c'est fini
      Sinon
         evaluerRetenue(T,k+1)
  Sinon
     T[k+1] <- suivant(T[k+1])
 
 
/*Prend une combinaison dans un tableau T, et génère le suivant*/
Procédure genererSuivant(Permutation T)
  Si estALaLimite(T[1])
   evoluerRetenue(T,1)
  Sinon
   T[1] <- suivant(T[1])

Ensuite, pour tous les obtenir, il suffit d'appeler genererSuivant tant que l'on souhaite et initialiser le tableau avec init() au début

Code :

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

1
2
3
4
5
6
7
 
Pour i = 1 à n
  T[i] <- init()
 
Tant que l'on a pas fini
  genererSuivant(T)
  ... faire ce qu' l'on doit faire avec la combinaisons

À noter que la procédure evoluerRetenue est terminale récursive, on peut facilement utiliser une simple boucle tant que.

Code :

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

1
2
3
4
5
6
Procédure evoluerRetenue(Permutation T, k)
 Tant que estALaLimite(T[k])
   T[k] <- init()
   k++
 
 T[k] <- suivant(T[k])

------------------------------------------------------------------

Typiquement pour des chiffres de 0 à 9, on peut définir les fonctions init, suivant et estALaLimite comme suit.

Code :

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

1
2
3
4
5
6
7
8
9
 
fonction init() -> Entier
  Retourne 0
 
fonction suivant(Entier i) -> Entier
  Retourne i+1 //normalement, ne doit pas être appelé au cas limite
 
fonction estALaLimite(Entier i) -> Booléen
  Retourne i==9

Par Florent Humbert



Si vous avez une autre méthode qui marche dans le cas général, n'hésitez pas.

[Jean-Marc.Bourguet]

Je ne sais pas combien de fois j'ai donné ces liens:

Generating all $n$-tuples: http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz
Generating all permutations: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz
Generating all combinations: http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz
Generating all partitions: http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz
Generating all trees: http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz
History of Combinatorial Generation: http://www-cs-faculty.stanford.edu/~knuth/fasc4b.ps.gz

[millie]

C'était juste pour la FAQ interne au site, donc c'était pas mal d'avoir quelque chose en français écrit par un membre de ce site

Je ne sais pas combien de fois j'ai donné ces liens:

Et donc comme ça, on pourra donner un lien en français sur DVP

[Jean-Marc.Bourguet]

Je répondais à la question "est-ce qu'il y a une autre méthode". Knuth en donne plusieurs avec des propriétés différentes. Il y a un intérêt à avoir un document plus accessible et en français, mais qui se mets à le rédiger devrait au moins aller voir cette source.

[Matthieu Brucher]

Et comme dans la FAQ on peut mettre des liens en plus, ça sera écrit une fois pour toutes

[PRomu@ld]

Et comme dans la FAQ on peut mettre des liens en plus, ça sera écrit une fois pour toutes

Très bonne idée.
Mais il faudra que l'on pense éventuellement à faire une traduction, ça pourrait être intéressant.

[Jean-Marc.Bourguet]

Commence par avoir l'accord de Knuth et d'Addison-Wesley avant de te lancer dans la traduction si tu veux la distribuer. Les versions definitives de ces fascicules sont vendus.

[Zavonen]

Si vous avez une autre méthode qui marche dans le cas général, n'hésitez pas.

Un algo récursif est facile à écrire et à implémenter dans n'importe quel langage, j'en ai soumis un en Java dans une autre discussion.
Pour un algo itératif on peut faire comme cela:
On travaille pour simplifier avec les n entiers: 0, 1, 2, ...,n-1
Pour permuter n'importe quoi il suffira d'utiliser un dictionnaire et de convertir chaque permutation.
Je suppose connu ce qu'est un cycle, et ses propriétés.
On considère d'abord le cycle C0 qui fait tourner les deux derniers entiers (n-2,n-1)
Puis le cycle C1 qui fait tourner les trois derniers (n-3,n-2,n-1)
Jusqu'au cycle Cn-1 qui fait tourner tous les entiers.
Ensuite on procède comme cela:
On part de l'unique liste contenant la liste identique
Soit [[0,1,...,n-1]]
On applique à tous les éléments de la liste les deux permutations
C0 et C0*C0=Id, on obtient 2 éléments
[[0,1,...n-2,n-1][0,1,...,n-1,n-2]]
On applique à la nouvelle liste obtenue les trois permutations:
C1, C1*C1, C1*C1*C1=Id
On obtient une liste de 6 éléments, tous forcément distincts car le n-3 'circule'.
Et on itére le processus.On obtient à la fin n! permutations toutes distintes, on les a donc toutes.
Cela revient à dire que le groupe symétrique d'ordre n est engendré par les n-1 cycles qui précèdent.
Voici ce que cela donne, par exemple en Python:

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
def cycle (n,p):
    L=[]
    for i in range(0,n-p):
        L.append(i)
    for i in range(n-p,n-1):
        L.append(i+1)
    L.append(n-p)
    return L
 
 
def compose (P1,P2):
    P3=[]
    for i in range(0,len(P1)):
        P3.insert(i,P2[P1[i]])
    return P3
 
def puissance (P,n):
    PUISS=[]
    for i in range (0,len(P)):
        PUISS.append(i)
    if i==0:
        return PUISS
    else:
        for i in range(0,n):
            PUISS=compose(PUISS,P)
        return PUISS
 
def permutations (n):
    CYCLES=[]
    for i in range (0,n-1):
        CYCLES.append(cycle(n,2+i))
    PERM1=[cycle(n-1,0)]
    for i in range (0,n-1):
        PERM2=[]
        for j in range (0,i+2):
            for k in range (0, len(PERM1)):
                PERM2.append(compose(PERM1[k],puissance(CYCLES[i],j)))
        PERM1=PERM2
    return PERM2
 
 
print permutations(5)

[mchk0123]

Une manière élégante et rapide (à l'exécution) d'implémenter l'algorithme de millie est de passer en représentation binaire.

Dans un premier temps, supposons que le nombre de chiffres est une puissance de 2 (par exemple 8 symboles).

Si on veut un nombre à 4 chiffres (exemple donné au hazard) :

c1 | c2 | c3 | c4

100 | 010 | 110 | 101

Ensuite il suffit de ne faire que ajouter +1 au nombre pour avoir la combinaison suivante. Le tout dans une simple boucle.

Et on obtient ce que l'on cherche sans récursion, avec une simple itération.

Dans un deuxième temps, si le nombre de chiffres n'est pas une puissance 2 ; il suffit de prendre la puissance de 2 la plus proche immédiatement supérieure. On à alors deux solutions possibles :

- vérifier à chaque itération si un des chiffres est trop grand (on ignore le nombre actuellement généré).
- utiliser un tableau de correspondance : chiffre binaire <-> symbole de l'alphabet. Pour les chiffres sans équivalence de symbole, on peut utiliser une valeur sentinelle (par exemple 1111).

[Zavonen]

Une nouvelle version itérative plus simple que mon ancienne proposition:

Code Python :

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
# génération des permutations d'un ensemble fini
# par un procédé itératif utilisant les générateurs de python
 
# fonction d'insertion
def ins(X,i,L):
    R=L[:] #copie de L
    R.insert(i,X) # insertion de X à l'index i dans R
    return R
 
# fait tourner X dans L à toutes les positions
def turn (X,L):
    return [ins(X,i,L) for i in range(0,len(L)+1)]
 
# un générateur
def permutations():
    i,P=0,[[]]
    yield P # stoppe l'exécuton pour la reprendre à cet endroit précis
    while True: # fait passer d'une génération à la suivante
        i=i+1
        Q=[turn(i,X) for X in P]
        P=reduce( lambda x,y:x+y,Q) # concaténation à répétition
        yield P #stoppe l'exécution pour la reprendre à cet endroit précis
 
def main():
    Perm=permutations()
    for i in range(0,6): # permutations d'un ensemble à 5 éléments
        X=Perm.next()
    print len(X)
    print X
 
if __name__ == '__main__':
    main()

[pseudocode]

Puisqu'on en est aux permutations en itératif, la version java:

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
 
public class Permutation<T> {
	private int[] state = null;
	private int   position = 0;
	private T[]   array = null;
 
	public Permutation(T[] data) {
		this.array = data;
		this.state = new int[data.length];
		this.position = 0;
	}
 
	public boolean next() {
		if (position==0) {position++; return true;}
		while(position<state.length) {
			if (state[position]<position) {
				int index = (position%2)==0 ? 0 : state[position];
				swap(position,index);
				state[position]++; position=1;
				return true;
			} else {
				state[position]=0;
				position++;
			}
		}
		return false;		
	}
 
	private void swap(int i, int j) {
		T tmp = array[i];
		array[i]=array[j];
		array[j]=tmp;
	}
}

Et un petit exemple d'utilisation:

Code java :

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

1
2
3
4
5
6
7
 
Character[] sample = new Character[] {'a','b','c','d'};
 
Permutation<Character> permut = new Permutation<Character>(sample);
 
while(permut.next())
	System.out.println(Arrays.toString(sample));

[SpiceGuid]

La question est souvent posée sous la forme combinaisons de ... mais il s'agit bien de permutations et non de combinaisons.

D'ailleurs on pourrait généraliser aux arrangements.

Un algo récursif est facile à écrire et à implémenter dans n'importe quel langage, j'en ai soumis un en Java dans une autre discussion.

Si c'est récursif alors c'est probablement celui-ci:

Code OCaml :

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

1
2
3
4
5
6
7
8
9
let rec distribute a l =
  match l with
  | []   -> [[a]]
  | h::t -> (a::l) :: (List.map (fun x -> h::x) (distribute a t))

let rec permute l =
  match l with
  | []   -> [[]]
  | h::t -> List.flatten (List.map (distribute h) (permute t))

Une variante importante pour les jeux c'est le mélange (obtenir une permutation):

• le mélange d'un singleton est ce même singleton
• on pioche un élément parmi n
• récursivement on réclame un mélange des n-1 éléments restants