Outil pour calculer le rang d'une combinaison mathématique (ou inversement, calculer une combinaison à partir d'un rang), c'est-à-dire la position d'une combinaison dans la liste croissante des combinaisons possibles générées.
Rang d'une Combinaison - dCode
Catégorie(s) : Combinatoire
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Ecrire à dCode !
Outil pour calculer le rang d'une combinaison mathématique (ou inversement, calculer une combinaison à partir d'un rang), c'est-à-dire la position d'une combinaison dans la liste croissante des combinaisons possibles générées.
Le rang d'une combinaison est la position d'une combinaison dans la liste de toutes les combinaisons possibles triées par ordre croissant.
Exemple : Toutes les combinaisons de 2 éléments parmi 4 sont : (1,2),(1,3),(1,4),(2,3),(2,4),(3,4), donc le rang de la combinaison (1,2) est 1, le rang de la combinaison (2,4) est 5
Avec $ c_i $ les éléments par ordre croissant $ c_1, c_2, \cdots, c_k $ d'une combinaison de $ k $ éléments et $ n $ le nombre total d'éléments, la formule pour calculer le rang sans avoir à lister toutes les combinaisons est $$ \binom{n}{k} - \binom{n-c_1}{k} - \binom{n-c_2}{k-1} - \cdots - \binom{n-c_k}{1} $$
Exemple : Calculer le rang de la combinaison (1,3) parmi les combinaisons de 2 parmi 4 $ \binom{4}{2} $, c'est prendre $ n = 4, k = 2, c_1 = 1, c_2 = 3 $ et calculer $$ \binom{4}{2} - \binom{4-1}{2} - \binom{4-3}{2-1} = 6 - 3 - 1 = 2 $$ donc (1,3) est au rang 2.
Cette méthode calcule la combinaison minimale minimisant $ n $ (ie. avec les plus petit nombres) pour une taille donnée $ k $.
Pour calculer une combinaison à partir d'un rang $ r $, déterminer le nombre d'élément $ k $ de la combinaison et répéter l'algorithme suivant :
1 - Calculer le plus grand nombre $ i $, tel que le nombre de combinaisons $ \binom{k}{i} $ soit inférieur ou égal au rang $ r $.
2 - Ajouter $ i $ au début de la combinaison, soustraire la valeur $ \binom{k}{i} $ au $ r $ et décrémenter $ k $ de $ 1 $
3 - Répéter les étapes 1 et 2 tant que $ k > 0 $
Exemple : Pour un rang $ r = 5 $ et une combinaison de $ k = 2 $ éléments
Etape 1 - calculer $ \binom{2}{2} = 1 < r $, $ \binom{3}{2} = 3 < r $ puis $ \binom{4}{2} = 6 > r $
Etape 2 - Combinaison = (4), $ r = 5-3 = 2 $, $ k = 1 $
Etape 1' - calculer $ \binom{1}{2} = 2 <= r $
Etape 2' - Combinaison = (2,4), $ r = 1 $, $ k = 0 $ - Fin
Donc la combinaison minimale de taille 2 et de rang 5 est (2,4)
dCode se réserve la propriété du code source de l'outil 'Rang d'une Combinaison' en ligne. Sauf code licence open source explicite (indiqué CC / Creative Commons / gratuit), tout algorithme, applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toute fonction (convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codé en langage informatique (PHP, Java, C#, Python, Javascript, Matlab, etc.) aucune donnée, script ou accès API ne sera cédé gratuitement, idem pour télécharger Rang d'une Combinaison pour un usage hors ligne, PC, tablette, appli iPhone ou Android !
Rendez-vous sur notre communauté Discord pour participer au forum d'entraide !