homechevron_rightLas étudechevron_rightMath

Combinatoire. Générateur de combinaisons.

Combinatoire. Générateur de combinaisons de m depuis n.

Ce calculateur génère les combinaisons possibles de m éléments depuis l'ensemble d'éléments de taille n. Le nombre de combinaisons possibles, tel que montré dans Combinatoire. Combinaisons, arrangements et permutations est
C_{n}^m=\frac{n!}{m!(n-m)!}

La description de l'algorithme de génération est en-dessous du calculateur

PLANETCALC, Combinatoire. Générateur de combinaisons.

Combinatoire. Générateur de combinaisons.

Ensemble

objets par page:

Combinaisons
Enregistrez le calcul pour le réutiliser la prochaine fois, pour extension l'intégrer dans votre site Web ou share le partager avec vos amis.

Algorithme

Les combinaisons sont générées dans l'ordre lexicographique. L'algorithme utilise les index des éléments de l'ensemble.
Voici un exemple qui vous montre comment cela fonctionne :
Supposez que nous ayons un ensemble de 5 éléments avec les index 1 2 3 4 5 (commençant à 1) et que nous ayons besoin de générer toutes les combinaisons de taille m = 3.
Tout d'abord, nous initialisons la première combinaison de taille m - index dans l'ordre croissant
1 2 3
Nous commençons par vérifier le dernier élément (soit i = 3). Si la valeur est inférieur à n - m + i, alors elle est incrémentée de 1.
1 2 4
Une fois de plus, nous vérifions le dernier élément, et puisqu'il est toujours inférieur à n - m + i, il est incrémenté de 1.
1 2 5
Désormais, il a la valeur maximale autorisée : n - m + i = 5 - 3 + 3 = 5 donc nous passons à l'élément précédent (i = 2)
Si sa valeur est inférieure à n - m + i, alors elle est incrémentée de 1 et tous les éléments suivant sont fixés à la valeur qui les précède plus 1.
1 (2+1)3 (3+1)4 = 1 3 4
Ensuite, nous recommençons depuis le dernier élément i = 3
1 3 5
Retour à i = 2
1 4 5
Désormais, il est finalement égal à n - m + i = 5 - 3 + 2 = 4, donc nous pouvons passer au premier élément (i = 1)
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Et ensuite,
2 3 5
2 4 5
3 4 5 - la dernière combinaison puisque toutes les valeurs sont fixées aux valeurs maximales possibles de n - m + i.

commentaires