Combinatoire. Générateur de combinaisons.

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

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

Combinatoire. Générateur de combinaisons.



Ensemble

	La valeur
		

Combinaison de taille m

Calculer

Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.

Télécharger 

 Lien  sauvegarder  Widget

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.