Combinaison par indice lexicographique

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.

Combinaison par indice

Taille de l'ensemble n

Taille de la combinaison k

Indice lexicographique

Calculer

Combinaison

 

Nombre total de combinaisons

 

 Lien  sauvegarder  Widget

Trouver la combinaison selon son indice lexicographique

Ce calculateur utilise un algorithme décrit par James McCaffrey¹.

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.