Rang d'une Combinaison

Le rang d'une combinaison correspond à sa position dans la liste de toutes les combinaisons possibles, triées par ordre lexicographique croissant. Sur cette page, dCode indexe le rang à partir de $ 1 $.

Pour une combinaison de $ k $ éléments notée $ (c_1, c_2, \cdots, c_k) $ avec $ 1 \le c_1 < c_2 < \cdots < c_k \le n $. Le rang $ r $ de cette combinaison parmi toutes les combinaisons de $ k $ éléments choisis parmi $ n $ peut être calculé sans les énumérer grâce à la formule : $$ r = \binom{n}{k} - \binom{n-c_1}{k} - \binom{n-c_2}{k-1} - \cdots - \binom{n-c_k}{1} $$

Cette formule repose sur le comptage de toutes les combinaisons lexicographiquement plus grandes que la combinaison étudiée.

L'algorithme repose sur le principe inverse du calcul de rang : il consiste à reconstruire progressivement les éléments de la combinaison en utilisant des coefficients binomiaux.

Pour une combinaison de taille $ k $ et un rang $ r $ :

1 - Initialiser une liste vide pour la combinaison

2 - Pour chaque position $ j $ allant de $ k $ à $ 1 $, déterminer le plus grand entier $ c $ tel que $ \binom{c}{j} < r $

3 - Ajouter $ c + 1 $ au début de la combinaison.

4 - Mettre à jour le rang : $ r = r - \binom{c}{j} $

5 - Répéter les étapes 2, 3 et 4 pour chaque valeur de $ j $, en décrémentant $ j $ de $ 1 $ à chaque itération, jusqu'à atteindre $ j = 1 $