Lister toutes les combinaisons
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.
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.
Réponses
-
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\} -
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.
-
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]
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres