Le laboratoire de science des données
Combinaisons mathématiques légères utilisant C#
Après avoir discuté précédemment des permutations, le Dr. James McCaffrey de Microsoft Research utilise des exemples pas à pas et des présentations de code complet pour explorer les combinaisons.
Une combinaison mathématique de base zéro (n, k) est un sous-ensemble de k entiers de 0 à n-1. Par exemple, si n = 5 et k = 3 il y a 10 combinaisons :
0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 4
Il est habituel de lister les combinaisons dans ce qu’on appelle l’ordre lexicographique. Si chaque combinaison est interprétée comme un entier ordinaire, les combinaisons sont répertoriées de la plus petite (12) à la plus grande (234).
Le nombre de (n,k) combinaisons est n! / (k! * (nk)!) où n! est factoriel(n) = n * (n-1) * (n-2) * . . 1. La fonction est souvent appelée Choose(). Par exemple, Choisissez(5, 3) = 5 ! / (3 ! * (5-3) !) = 120 / (6 * 2) = 120 / 12 = 10.
Le nombre de combinaisons devient très, très grand à mesure que n et k augmentent. Par exemple, Choisissez(500, 100) =
204,169,423,593,847,671,561,387,240,724,193,094, 030,165,460,090,325,932,474,143,661,505,758,330, 944,415,515,994,945,349,100,113,181,687,417,345
qui est nettement plus grand que le nombre estimé d’atomes dans l’Univers.
Pour gérer les combinaisons à l’aide du langage C #, il est nécessaire d’utiliser le type de données BigInteger qui peut gérer des valeurs arbitrairement grandes.
Les combinaisons mathématiques sont liées aux permutations mathématiques, mais très différentes de celles-ci. Une permutation mathématique d’ordre n à base zéro est un réarrangement des nombres entiers de 0 à n-1. Par exemple, une permutation d’ordre n = 5 est (2, 0, 1, 4, 3).
Une bonne façon de voir où va cet article est de jeter un coup d’œil à la capture d’écran d’un programme de démonstration dans Figure 1. La démo montre comment créer et afficher une combinaison (n,k), calculer Choose(n,k) en utilisant le type BigInteger, afficher toutes les combinaisons (n,k) en utilisant une fonction Successor() et calculer directement un élément de combinaison spécifique .
Cet article suppose que vous avez une compétence de programmation intermédiaire ou supérieure avec le langage C #, mais ne suppose pas que vous savez quoi que ce soit sur les combinaisons mathématiques. Le code de démonstration complet est présenté dans cet article et est également disponible dans le téléchargement qui l’accompagne. Toutes les vérifications d’erreur normales ont été supprimées pour garder les idées principales aussi claires que possible.
Pour créer le programme de démonstration, j’ai utilisé Visual Studio 2022 (l’édition communautaire gratuite) avec .NET 6 (malgré le nouveau modèle de console “déprouvé”). Cependant, la démo n’a pas de dépendances significatives, donc toutes les versions relativement récentes de VS et .NET peuvent être utilisées.
Définir et afficher une combinaison
La manière la plus simple de définir une combinaison mathématique consiste à utiliser un tableau d’entiers. Le programme de démonstration implémente une fonction MakeComb() comme :
static int[] MakeComb(int n, int k)
{
int[] result = new int[k];
for (int i = 0; i < k; i++)
result[i] = i;
return result;
}
La fonction MakeComb() peut être appelée ainsi :
int n = 5; int k = 3;
int[] c = MakeComb(n, k);
Console.WriteLine("Initial Combination(n=5, k=3) is: ");
ShowComb(c);
La fonction ShowComb() est définie comme :
static void ShowComb(int[] comb)
{
int n = comb.Length;
for (int i = 0; i < n; ++i)
Console.Write(comb[i] + " ");
Console.WriteLine("");
}
Une conception alternative consiste à définir une classe de combinaison dédiée, mais dans la plupart des scénarios, l'utilisation d'un tableau d'entiers est simple et efficace.
Définition d'une fonction Choose
Le programme de démonstration utilise le type BigInteger pour définir une fonction Choose() comme présenté dans Liste 1. La fonction utilise plusieurs astuces mathématiques pour plus d'efficacité. La première astuce est basée sur l'idée que Choose(n, k) = Choose(n, nk), par exemple, Choose(100, 97) a la même valeur que Choose(100, 3). Cette astuce est utile car les petites valeurs de k sont plus faciles à calculer.
La deuxième astuce est mieux expliquée par un exemple concret. Le calcul de Choose() à l'aide de la définition de base est inefficace car le n! et k! les termes factoriels peuvent être très grands. Une autre définition de Choose() ressemble à ceci :
Choose(100, 3) = (100 * 99 * 98) / (3 * 2 * 1)
= 50 * 33 * 98
= 161,700
En mots, le dénominateur est k ! (qui, en utilisant la première astuce peut être petit) et le numérateur est k termes sous la forme n * (n-1) * (n-2) * . . . qui est beaucoup plus petit que n!
Liste 1 : Une fonction Choose()
using System.Numerics;
static BigInteger Choose(int n, int k)
{
// number combinations
if (n < 0 || k < 0)
throw new Exception("Negative argument in Choose()");
if (n < k) return 0; // special
if (n == k) return 1; // short-circuit
int delta, iMax;
if (k < n - k) // ex: Choose(100,3)
{
delta = n - k; iMax = k;
}
else // ex: Choose(100,97)
{
delta = k; iMax = n - k;
}
BigInteger ans = delta + 1;
for (int i = 2; i <= iMax; ++i)
ans = (ans * (delta + i)) / i;
return ans;
}
Le type BigInteger est défini dans l'espace de noms System.Numerics. Le code de démonstration définit Choose(n, k) comme 0 lorsque n < k comme cas particulier.
Le programme de démonstration appelle la fonction Choose() comme ceci :
BigInteger numCombs = Choose(5,3);
Console.WriteLine("Number of n=5, k=3 combs is: ");
Console.WriteLine(numCombs);
numCombs = Choose(100, 10);
Console.WriteLine("Number ways choose 10 from 100: ");
Console.WriteLine(numCombs.ToString("N0"));
Étant donné que le résultat de la fonction Choose() peut être très volumineux, il est souvent utile d'utiliser la spécification de formatage "N0" pour placer des virgules dans la sortie.
Définition d'une fonction successeur
Définir une fonction qui renvoie la combinaison successeur d'une combinaison donnée est un problème bien connu. Le programme de démonstration définit une fonction Successor() dans Liste 2.
Liste 2 : La fonction Combination Successor()
static int[] Successor(int[] comb, int n, int k)
{
if (IsLast(comb, n, k) == true)
return null;
int[] result = new int[k]; // make copy
for (int i = 0; i < k; ++i)
result[i] = comb[i];
int idx = k - 1;
while (idx > 0 && result[idx] == n - k + idx)
--idx;
++result[idx];
for (int j = idx; j < k - 1; ++j)
result[j + 1] = result[j] + 1;
return result;
}
Supposons n = 10 et k = 6 et une combinaison actuelle est (0, 2, 3, 4, 8, 9). La combinaison successeur est (0, 2, 3, 5, 6, 7).
La fonction Successor() trouve d'abord l'index le plus à gauche (idx) de la valeur à incrémenter. Dans cet exemple idx = [3]. La valeur à [3] est 4 et il est incrémenté donnant un résultat intermédiaire de (0, 2, 3, 5, 8, 9). Ensuite, l'algorithme incrémente séquentiellement les valeurs de queue à droite de idx donnant le résultat successeur final de (0, 2, 3, 5, 6, 7).
Avec une fonction Successor() en main, il est possible de parcourir toutes les combinaisons avec du code comme :
int[] c = MakeComb(5, 3); // [0,1,2]
Console.WriteLine("All n=5, k=3 combinations: ");
while (c != null)
{
ShowComb(c);
c = Successor(c, n, k);
}
La fonction de démonstration Successor() renvoie null si la combinaison actuelle est la dernière combinaison. Par exemple, pour n = 8 et k = 3, la dernière combinaison dans l'ordre lexicographique est (5, 6, 7). Le programme de démonstration définit une fonction IsLast() comme :
static bool IsLast(int[] comb, int n, int k)
{
// is comb(8,3) like [5,6,7] ?
if (comb[0] == n - k)
return true;
else
return false;
}
La dernière combinaison (n, k) aura la forme (nk), (n-k+1), . . (n-1). En raison de l'ordre lexicographique, il suffit de vérifier la première valeur de la combinaison pour voir si elle est nk car cette condition n'est vraie que pour la dernière combinaison.
Le mème élément de combinaison lexicographique directement
Supposons que vous vouliez un élément de combinaison spécifique. Par exemple, toutes les combinaisons 10 n = 5, k = 3 sont :
[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
Vous voulez une fonction nommée Element qui accepte un index, m, et renvoie la combinaison spécifiée, par exemple, pour n = 5 et k = 3, Element(m=5) renvoie (0, 3, 4).
Parce qu'il n'y a que Choose(5, 3) = 10 combinaisons possibles, vous pouvez commencer par la combinaison initiale (0, 1, 2) puis appeler la fonction Successor() dans une boucle for avec cinq itérations et finir à la combinaison souhaitée combinaison.
Mais cette approche simple ne fonctionne que pour de très petites valeurs de n et k. Assez étonnamment, il est possible d'écrire une fonction qui renvoie directement une combinaison spécifiée. Le programme de démonstration définit une fonction Element() dans Liste 3.
Liste 3 : Calcul direct du mème élément de combinaison
static int[] Element(BigInteger m, int n, int k)
{
// compute element [m] using the combinadic
BigInteger maxM = Choose(n, k) - 1;
if (m > maxM)
throw new Exception("m value is too large in Element");
int[] ans = new int[k];
int a = n;
int b = k;
BigInteger x = maxM - m; // x is the "dual" of m
for (int i = 0; i < k; ++i)
{
ans[i] = LargestV(a, b, x); // see helper below
x = x - Choose(ans[i], b);
a = ans[i];
b = b - 1;
}
for (int i = 0; i < k; ++i)
ans[i] = (n - 1) - ans[i];
return ans;
}
static int LargestV(int a, int b, BigInteger x)
{
int v = a - 1;
while (Choose(v, b) > x)
--v;
return v;
}
La fonction Element() appelle une fonction d'assistance LargestV(). La fonction Element() peut être appelée comme ceci :
int n = 100;
int k = 10;
BigInteger m = BigInteger.Parse("9999999999");
int[] c = Element(m, n, k);
Console.WriteLine("Combination [" + m + "] " +
" of C(n=100,k=10): ");
ShowComb(c);
L'algorithme de la fonction Element() est beau mais assez compliqué. L'algorithme est basé sur l'expression d'un entier sous la forme d'un "combinadique", qui est une combinaison linéaire des valeurs de la fonction Choose(). Vous pouvez trouver une explication détaillée de l'algorithme dans mon article de blog.
Emballer
Les exemples de cet article utilisent des combinaisons de base zéro. Ceci est pratique car dans de nombreuses utilisations pratiques des combinaisons, les valeurs de combinaison correspondent aux indices de tableau. Dans un contexte mathématique pur, les combinaisons à base un sont plus courantes.
Une idée étroitement liée aux combinaisons mathématiques porte le nom plutôt étrange de "nombres de Stirling du second type", généralement écrit sous la forme S(n, k). La fonction renvoie le nombre de façons de partitionner n éléments en k sous-ensembles. Par exemple, supposons n = 4 et k = 2, alors S(4, 2) = 7. Si les n éléments sont (0, 1, 2, 3) alors les 7 partitions sont : (0 | 123), (1 | 023), (2 | 013), (3 | 012), (01 | 23), (02 | 13) et (03 | 12). Il est possible d'implémenter la fonction S(n, k) en utilisant les idées présentées dans cet article.
A propos de l'auteur
Dr. James McCaffrey travaille pour Microsoft Research à Redmond, Wash. Il a travaillé sur plusieurs produits Microsoft, dont Azure et Bing. Jacques est joignable au [email protected].
.