Mélanger un tableau en C#

Le mélange réordonne aléatoirement les éléments déjà présents dans un tableau ; il n’ajoute ni ne supprime aucune valeur. L’algorithme Fisher–Yates est l’approche standard en place : choisir un index dans la partie qui n’est pas encore fixée, échanger cette valeur avec celle de la position courante, puis réduire la partie restante. Utilisez Random pour les usages courants d’une application. Utilisez RandomNumberGenerator lorsque l’imprévisibilité est importante pour la sécurité, tout en appliquant un algorithme de mélange correct.

Mélanger un tableau avec Fisher–Yates

Fisher–Yates parcourt le tableau du dernier index vers le premier. À la position i, il choisit uniformément j entre zéro et i, puis échange les deux valeurs. À chaque itération, une position est fixée et la plage se réduit. Si les choix bornés sont uniformes, toutes les permutations ont la même probabilité.

Exécutez cet exemple complet :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

using System;

class Program
{
    static void Shuffle<T>(T[] items, Random random)
    {
        for (int i = items.Length - 1; i > 0; i--)
        {
            int j = random.Next(i + 1);
            (items[i], items[j]) = (items[j], items[i]);
        }
    }

    static void Main()
    {
        int[] values = { 1, 2, 3, 4, 5 };
        Shuffle(values, new Random());
        Console.WriteLine(string.Join(", ", values));
    }
}

Pour un tableau de longueur n, la boucle effectue n - 1 échanges ; elle s’exécute donc en temps linéaire et modifie directement le tableau d’entrée. Il n’est pas nécessaire de choisir une valeur pour le dernier élément restant. Un tableau vide ou contenant un seul élément ne nécessite donc aucun échange et reste inchangé. En passant l’instance de Random à la méthode, l’appelant peut également réutiliser le même générateur pour plusieurs mélanges.

Utiliser Random pour un mélange courant

Pour les jeux, l’échantillonnage et les autres tâches sans enjeu de sécurité, Random fournit les valeurs bornées dont Fisher–Yates a besoin. random.Next(i + 1) renvoie un entier compris entre zéro inclus et i + 1 exclu ; chaque position encore disponible peut donc être choisie. L’exemple complet ci-dessus utilise cette méthode et conserve tous les éléments du tableau d’entrée.

Créez une instance de Random et réutilisez-la si l’application doit effectuer plusieurs mélanges. Sur d’anciennes versions du runtime, créer plusieurs générateurs à la suite dans un court intervalle peut produire des séquences corrélées. Le résultat varie d’une exécution à l’autre : ne comptez donc pas sur un ordre particulier. Le mélange modifie l’agencement, pas les valeurs ni leur nombre d’occurrences.

Utiliser RandomNumberGenerator pour un mélange sécurisé

Lorsque l’ordre influe sur une décision de sécurité, utilisez des octets aléatoires cryptographiques comme source des choix de Fisher–Yates. La conversion en valeur bornée doit elle aussi être sans biais : prendre le reste d’un entier aléatoire peut favoriser certains résultats si le nombre d’entiers possibles n’est pas divisible par la borne. L’échantillonnage par rejet écarte le petit intervalle excédentaire avant de calculer le reste.

Cet exemple complet utilise RandomNumberGenerator.Create() et son API GetBytes(byte[]), qui remplit un tableau d’octets, puis applique la même boucle d’échanges décroissante :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

using System;
using System.Security.Cryptography;

class Program
{
    static ulong NextBelow(RandomNumberGenerator random, ulong bound)
    {
        byte[] bytes = new byte[8];
        ulong threshold = unchecked(0UL - bound) % bound;
        ulong value;

        do
        {
            random.GetBytes(bytes);
            value = BitConverter.ToUInt64(bytes, 0);
        }
        while (value < threshold);

        return value % bound;
    }

    static void Shuffle<T>(T[] items, RandomNumberGenerator random)
    {
        for (int i = items.Length - 1; i > 0; i--)
        {
            int j = (int)NextBelow(random, (ulong)i + 1);
            (items[i], items[j]) = (items[j], items[i]);
        }
    }

    static void Main()
    {
        int[] values = { 1, 2, 3, 4, 5 };
        using (RandomNumberGenerator random = RandomNumberGenerator.Create())
        {
            Shuffle(values, random);
        }
        Console.WriteLine(string.Join(", ", values));
    }
}

Le calcul du seuil rejette les valeurs situées avant la limite de la plus grande portion divisible uniformément, ce qui évite le biais du modulo pour chaque borne. RandomNumberGenerator rend les choix plus difficiles à prévoir ; à lui seul, il ne rend pas uniforme un algorithme biaisé et ne sécurise pas une conception d’application vulnérable. Utilisez-le uniquement lorsque l’imprévisibilité est nécessaire, car il entraîne davantage de surcoût que Random.

Pourquoi OrderBy avec Random ne garantit pas un mélange fiable

Trier des éléments selon des clés aléatoires générées n’équivaut pas à choisir directement dans la plage restante et à échanger les éléments. Cette méthode effectue un tri, qui demande généralement plus de travail que la boucle linéaire Fisher–Yates. Les clés de Random peuvent aussi entrer en collision ; l’ordre des éléments ex æquo dépend alors du comportement du tri. Cette méthode peut sembler convenir à une démonstration rapide, mais elle n’est pas recommandée pour obtenir une permutation uniforme. L’algorithme Fisher–Yates rend explicites les choix et la réduction progressive de leurs bornes.

Choisir la bonne approche

Utilisez Fisher–Yates avec Random pour un mélange courant, et le même algorithme avec RandomNumberGenerator lorsque la sécurité dépend d’un ordre imprévisible. Dans les deux cas, des choix bornés sans biais sont nécessaires pour obtenir un résultat uniforme. Réutilisez le générateur, passez le tableau que vous souhaitez modifier et gardez à l’esprit que l’ordre peut varier à chaque exécution. Évitez le tri par clés aléatoires si vous avez besoin d’un mélange clair, efficace et uniforme.