Le laboratoire de science des données
Permutations mathématiques légères utilisant C#
Préparez-vous à utiliser le type de données BigInteger en tant que Dr. James McCaffrey de Microsoft Research démontre des permutations mathématiques de base zéro avec C#.
Une permutation mathématique de base zéro d’ordre n est un réarrangement des entiers 0 à n-1. Par exemple, si n = 5, alors deux permutations possibles sont (0, 1, 2, 3, 4) et (3, 0, 4, 2, 1). Le nombre total de permutations pour l’ordre n est factoriel (n), généralement écrit comme n ! et calculé comme n * (n-1) * (n-2) * . . 1. Par exemple, 5 ! = 5 * 4 * 3 * 2 * 1 = 120.
Le nombre de permutations devient très, très grand lorsque n augmente. Par exemple, 30 ! = 265 252 859 812 191 058 636 308 480 000 000, ce qui est largement supérieur à l’âge estimé de l’univers en secondes (environ 13,8 milliards d’années). Pour gérer les permutations à 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.
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 permutation d’ordre n, calculer n ! en utilisant le type BigInteger, affichez toutes les permutations d’ordre n à l’aide d’une fonction Successor() et calculez directement un élément de permutation spécifique.
Cet article suppose que vous avez des compétences de programmation intermédiaires ou supérieures avec le langage C #, mais ne suppose pas que vous savez quoi que ce soit sur les permutations 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 bizarre). 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 permutation
La manière la plus simple de définir une permutation mathématique consiste à utiliser un tableau de type entier. Le programme de démonstration implémente une fonction MakePerm() comme :
static int[] MakePerm(int order)
{
int[] result = new int[order];
for (int i = 0; i < order; i++)
result[i] = i;
return result;
}
La fonction MakePerm() peut être appelée ainsi :
int[] p = MakePerm(4); // [0,1,2,3]
Console.WriteLine("Initial permutation order 4 is: ");
ShowPerm(p);
La fonction ShowPerm() est définie comme suit :
static void ShowPerm(int[] perm)
{
int order = perm.Length;
for (int i = 0; i < order; ++i)
Console.Write(perm[i] + " ");
Console.WriteLine("");
}
Une conception alternative consiste à définir une classe Permutation dédiée, mais dans la plupart des scénarios, l'utilisation d'un tableau d'entiers est simple et efficace.
Définir une fonction factorielle
Le programme de démonstration utilise le type BigInteger pour définir une fonction factorielle comme :
using System.Numerics;
static BigInteger Factorial(int n)
{
if (n == 0 || n == 1)
return BigInteger.One;
BigInteger ans = BigInteger.Parse("1"); // alternative
for (int i = 1; i <= n; ++i)
ans *= i;
return ans;
}
Le type BigInteger est défini dans l'espace de noms System.Numerics. Dans la plupart des cas 0 ! est défini comme étant 1 afin que le code de démonstration effectue une vérification de court-circuit. Le code montre qu'une valeur BigInteger peut être créée à l'aide de la méthode Parse() ou à l'aide des propriétés de raccourci BigInteger.One ou BigInteger.Zero.
Le programme de démonstration appelle la fonction Factorial() comme ceci :
BigInteger numPerms = Factorial(4);
Console.WriteLine("Total permutations order 4 is: ");
Console.WriteLine(numPerms);
numPerms = Factorial(50);
Console.WriteLine("Total permutations order 50 is: ");
Console.WriteLine(numPerms.ToString("N0"));
Étant donné que le résultat de la fonction Factorial() 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
Les six permutations d'ordre n = 3 sont :
0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
Il est habituel de lister les permutations dans ce qu'on appelle l'ordre lexicographique. Si chaque permutation est interprétée comme un entier, elles sont répertoriées du plus petit (12) au plus grand (210). Définir une fonction qui renvoie la permutation successeur à une permutation donnée est un problème bien connu. Le programme de démonstration définit une fonction Successor() dans Liste 1.
Liste 1 :
La fonction successeur de permutation()
static int[] Successor(int[] perm)
{
int order = perm.Length; // ex: order 5
// is perm like [4,3,2,1,0] so no successor?
if (IsLast(perm) == true)
return null;
int[] result = new int[order];
for (int k = 0; k < order; ++k)
result[k] = perm[k];
int left, right;
left = order - 2; // find left value
while ((result[left] > result[left + 1]) && (left >= 1))
--left;
right = order - 1; // first value gt left
while (result[left] > result[right])
--right;
int tmp = result[left]; // swap [left] and [right]
result[left] = result[right];
result[right] = tmp;
int i = left + 1; // order the tail
int j = order - 1;
while (i < j)
{
tmp = result[i];
result[i++] = result[j];
result[j--] = tmp;
}
return result;
}
Supposons n = 6 et une permutation actuelle est (5, 4, 1, 3, 2, 0). La permutation successeur est (5, 4, 2, 0, 1, 3).
L'algorithme de la fonction Successor() trouve les emplacements d'index de deux valeurs à échanger, dans ce cas left = [2] et à droite = [4]. Une fois les deux valeurs à gauche et à droite échangées, le résultat intermédiaire est (5, 4, 2, 3, 1, 0). Ensuite, l'algorithme trouve la queue, qui sont les valeurs à [left+1] à la fin, puis trie les valeurs de queue de la plus petite à la plus grande. Dans cet exemple, les valeurs de queue du résultat intermédiaire sont (3, 1, 0). Après avoir trié les valeurs de queue, le résultat final du successeur est (5, 4, 2, 0, 1, 3).
Avec une fonction Successor() en main, il est possible de parcourir toutes les permutations avec du code comme :
int[] p = MakePerm(4); // [0,1,2,3]
Console.WriteLine("All permutations order 4: ");
while (p != null)
{
ShowPerm(p);
p = Successor(p);
}
La fonction de démonstration Successor() renvoie null si la permutation actuelle est la dernière permutation. Le programme de démonstration définit une fonction IsLast() comme :
static bool IsLast(int[] perm)
{
// is perm like [5,4,3,2,1,0] ?
int order = perm.Length;
if (perm[0] != order - 1) return false;
if (perm[order - 1] != 0) return false;
for (int i = 0; i < order - 1; ++i) {
if (perm[i] < perm[i + 1])
return false;
}
return true;
}
La dernière permutation d'ordre n aura la forme (n-1), (n-2), . . 0. La fonction IsLast() effectue une vérification facultative du premier et du dernier élément de la permutation pour voir si un retour rapide de court-circuit est possible.
Le kème élément de permutation lexicographique directement
Supposons que vous souhaitiez un élément de permutation spécifique, par exemple la permutation k = [99] pour l'ordre n = 5. Parce qu'il n'y en a que 5 ! = 120 permutations possibles, vous pouvez commencer par la permutation initiale (0, 1, 2, 3, 4) puis appeler la fonction Successor() dans une boucle for avec 99 itérations et aboutir à la permutation souhaitée.
Cette approche ne fonctionne que pour de petites valeurs de n. Étonnamment, il est possible d'écrire une fonction qui renvoie directement une permutation spécifiée. Le programme de démonstration définit une fonction Element() dans Liste 2.
Liste 2 : Calcul direct du kième élément de permutation
static int[] Element(BigInteger k, int order)
{
// kth lexicographical element
if (k >= Factorial(order))
throw new Exception("k too large in Element");
int[] result = new int[order];
int[] factoradic = new int[order]; // factoradic of k
for (int j = 1; j <= order; ++j) // note: skip [0]
{
factoradic[order - j] = (int)(k % j);
k /= j;
}
for (int i = 0; i < order; ++i)
++factoradic[i];
result[order - 1] = 1; // last value set to 1
for (int i = order - 2; i >= 0; --i)
{
result[i] = factoradic[i];
for (int j = i + 1; j < order; ++j)
{
if (result[j] >= result[i])
++result[j];
}
}
for (int i = 0; i < order; ++i)
--result[i];
return result;
}
La fonction Element() peut être appelée comme ceci :
int order = 5; // 5! = 120
BigInteger k = BigInteger.Parse("99");
int[] p = Element(k, order);
Console.WriteLine("Permutation [" + k + "] order 5: ");
ShowPerm(p);
L'algorithme de la fonction Element() est l'un des plus fascinants et des plus beaux dans le domaine de la combinatoire mathématique. L'algorithme est basé sur l'expression d'un entier sous la forme d'un "factoradic", qui est une combinaison linéaire des valeurs de la fonction Factorial(). Vous pouvez trouver une explication détaillée de l'algorithme dans mon article de blog.
Emballer
Les exemples de cet article utilisent des permutations de base zéro. Ceci est pratique car dans de nombreuses utilisations pratiques des permutations, les valeurs de permutation correspondent aux indices de tableau. Dans un contexte mathématique pur, les permutations à base un sont plus courantes.
Un concept relativement rare lié aux permutations s'appelle les dérangements. Un dérangement est une permutation où aucun élément n'est dans sa position d'origine. Par exemple, si n = 4 il y en a 4 ! = 24 permutations, de (0, 1, 2, 3) à (3, 2, 1, 0). Pour n = 4 il y a neuf dérangements :
1 0 3 2 1 2 3 0 1 3 0 2 2 0 3 1 2 3 0 1 2 3 1 0 3 0 1 2 3 2 0 1 3 2 1 0
La permutation (1, 0, 2, 3) n'est pas un dérangement car 2 et 3 sont dans leurs positions d'origine. Mais (1, 0, 3, 2) est un dérangement car aucun des quatre éléments n'est dans sa position d'origine. En général, environ un tiers des permutations d'ordre n sont aussi des dérangements.
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].
.