[FAQ] Détermination de combinaisons

Version imprimable

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:

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:

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:

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:

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.

26/10/2006, 13h33
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
26/10/2006, 13h38
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 ;)

Citation:

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
26/10/2006, 13h56
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.
26/10/2006, 18h34
Matthieu Brucher

Et comme dans la FAQ on peut mettre des liens en plus, ça sera écrit une fois pour toutes :D
21/11/2006, 13h43
PRomu@ld

Citation:

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.
21/11/2006, 14h22
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.

Citation:

Envoyé par millie

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:

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)

04/04/2007, 20h58
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).

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

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
# 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()

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

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

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

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.

Citation:

Envoyé par Zavonen

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:

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