Lister toutes les combinaisons

kayy · June 2013

Bonjour,

J'ai la formule qui donne le nombre de Combinaisons possibles de k éléments parmi n.
Calcul_du_nombre_de_combinaisons

J'aimerais trouver l'algo qui permettrait de lister toutes ces combinaisons, avec ou sans permutation.
Il y a bien le paragraphe "Énumération des combinaisons" sur le même site mais je n'y comprends pas grand chose.
Quelqu'un pourrait m'aider svp ?
Merci.

joel_5632 · June 2013

bonjour

Soit un ensemble E de n éléments dont on veut lister toutes les parties (ou combinaisons)

On fait varier une variable i de 0 à $2^n - 1$

On considère cette variable i en binaire, çad $ i = i_{n-1} ... i_1 i_0$ avec $i_k = 0\;ou\; 1$

Si le bit $i_k$ vaut 1, alors on prend le k ième l'élément de E et on le met dans la partie F en cours de création.

par exemple E = \{a, b, c\}

i ___F
000 $\varnothing$
001 \{a\}
010 \{b\}
011 \{b, a\}
100 \{c\}
101 \{c, a\}
110 \{c, b\}
111 \{c, b, a\}

joel_5632 · June 2013

et si tu veux en plus toutes les permutations pour chacune des combinaisons, il y a cet algorithme décrit ici:

permut

et il en existe d'autres

Guego · June 2013

Pour lister les combinaisons, on peut le faire récursivement : pour obtenir une partie à $k$ éléments d'un ensemble à $n$ éléments, on prend un élément parmi les $n$ disponibles et on l'ajoute à une partie à $k-1$ éléments pris parmi les $n-1$ autres.

Braun · June 2013

Bonjour,
D'abord je ne suis pas certain d'avoir compris "ces combinaisons, avec ou sans permutation".
Mais le vocabulaire a peut être changé.
Ensuite, comme je ne suis pas très au fait en ce qui concerne les "algorythmes" ou "algorithmes", j'ai pris quelque minutes pour proposer un programme en Xlogo:

# Commande principale: combine

pour combine :l :r
si (egal? :r 1) [retourne maplist :l ] 
si (:r > compte :l) [retourne [] ] [retourne concat mapmp prem :l combine saufpremier :l (:r - 1) combine saufpremier :l :r ]
fin

pour concat :l1 :l2
si (vide? :l1) [retourne :l2] 
retourne mp prem :l1 concat saufpremier :l1 :l2 
fin

pour mapad :x :l
si (vide? :l) [retourne []]
retourne mp mp :x prem :l mapad :x saufpremier :l 
fin

pour maplist :l
si (vide? :l) [retourne []]
retourne mp mp prem :l [] maplist saufpremier :l 
fin

pour mapmp :x :l
si (vide? :l) [retourne []]
retourne mp mp :x prem :l mapad :x saufpremier :l 
fin

Just for fun

combine [a b c d e]

Lister toutes les combinaisons

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 22