Combinaison par indice lexicographique

Ce calculateur en ligne trouve la combinaisons par indice dans un ensemble lexicographique ordonné.

En mathématiques, l'ordre lexicographique (ou ordre lexical, ordre du dictionnaire ou ordre alphabétique) est une manière où les séquence (soit les mots) sont ordonnées alphabétiquement sur la base de l'ordre alphabétique de leurs composants (lettres). Il est souvent utilisé en combinatoires pour produire toutes les combinaisons possibles - elles sont générées dans l'ordre lexicographique.

Supposons que nous avons un ensemble de 5 éléments { 0 1 2 3 4 } et que nous voulons générer toutes les combinaisons de 3. Il y a 10 combinaisons au total et les voici dans l'ordre lexicographique.

0 : { 0 1 2 }
1 : { 0 1 3 }
2 : { 0 1 4 }
3 : { 0 2 3 }
4 : { 0 2 4 }
5 : { 0 3 4 }
6 : { 1 2 3 }
7 : { 1 2 4 }
8 : { 1 3 4 }
9 : { 2 3 4 }

Si vous voulez générer toutes les combinaisons possibles dans l'ordre lexicographique, vous pouvez utiliser le calculateur Combinatoire. Générateur de combinaisons.

Ainsi, ce calculateur donne une combinaison suivant son indice dans la liste lexicographique ordonnée de toutes les combinaisons. Bien sûre, il fait cela sans calculer toutes les combinaisons pour une question d'efficacité. Vous pouvez trouver la description de l'algorithme en-dessous du calculateur.

Remarque : l'indice est basée sur ZERO.

PLANETCALC, Combinaison par indice

Combinaison par indice

Combinaison
 
Nombre total de combinaisons
 

Trouver la combinaison selon son indice lexicographique

Ce calculateur utilise un algorithme décrit par James McCaffrey1.

Utilisons les notations et définitions suivantes :

  • n - nombre d'élement dans l'ensemble, soit 5
  • k - nombre d'élement dans la combinaison, soit. 3
  • N - nombre total de combinaisons, soit 10
  • indice de la combinaison dans la liste lexicographique, basé sur zéro, de 0 à N-1, soit 0 ... 9
  • indice double - indice opposé, la somme de l'indice et de son opposé donne N-1, soit pour l'indice 1; l'indice double est 8

Algorithme

  1. Trouver l'indice double pour un indice donné i en calculant (N-1) - i
  2. Trouver le combinadique de l'indice double, voir Systèmes numériques combinatoires
  3. Inverser chaque coefficient du combinadique c en calculant (n-1) - c
  4. Les coefficients résultants représentent la combinaison recherchée.

  1. James McCaffrey. Génération du m-ième élément lexicographique d'une combinaison mathématique. Magazine MSDN, juillet 2004 

URL copiée dans le presse-papiers
PLANETCALC, Combinaison par indice lexicographique

commentaires