Mische ein Array in C#

Beim Mischen werden die vorhandenen Elemente eines Arrays zufällig angeordnet; es werden keine Werte hinzugefügt oder entfernt. Der Fisher–Yates-Algorithmus ist das übliche Verfahren zum Mischen an Ort und Stelle: Wähle einen Index aus dem noch nicht festgelegten Bereich, tausche den dortigen Wert mit dem Wert an der aktuellen Position und verkleinere den Bereich. Für gewöhnliche Anwendungen eignet sich Random. Wenn Unvorhersehbarkeit aus Sicherheitsgründen wichtig ist, verwende RandomNumberGenerator und achte zugleich auf einen korrekten Mischalgorithmus.

Ein Array mit Fisher–Yates mischen

Fisher–Yates durchläuft das Array vom letzten Index bis zum Anfang. An Position i wählt der Algorithmus gleichverteilt einen Index j zwischen null und i und tauscht anschließend die beiden Werte. Bei jedem Durchlauf wird eine Position festgelegt und der Bereich verkleinert. Sind die begrenzten Zufallsauswahlen gleichverteilt, ist jede Permutation gleich wahrscheinlich.

Führe dieses vollständige Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

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));
    }
}

Bei einem Array der Länge n führt die Schleife n - 1 Vertauschungen aus. Sie läuft daher in linearer Zeit und verändert das Eingabearray direkt. Für das zuletzt verbleibende Element ist keine Auswahl nötig. Ein leeres Array oder ein Array mit nur einem Element benötigt folglich keine Vertauschungen und bleibt unverändert. Wenn du der Methode eine Random-Instanz übergibst, kann der Aufrufer denselben Zufallszahlengenerator für mehrere Mischvorgänge wiederverwenden.

Random für gewöhnliche Mischvorgänge verwenden

Für Spiele, Stichproben und andere Aufgaben ohne Sicherheitsbezug liefert Random die begrenzten Zufallswerte, die Fisher–Yates benötigt. random.Next(i + 1) gibt eine ganze Zahl von null bis ausschließlich i + 1 zurück. Dadurch kommt jede noch verfügbare Position infrage. Das vollständige Beispiel oben verwendet diese Methode und erhält alle Elemente des Eingabearrays.

Erzeuge eine Random-Instanz und verwende sie wieder, wenn eine Anwendung mehrere Mischvorgänge ausführt. Werden Zufallszahlengeneratoren in kurzen Abständen wiederholt neu erstellt, können auf älteren Laufzeitversionen korrelierte Zahlenfolgen entstehen. Das Ergebnis kann sich von Lauf zu Lauf ändern; verlasse dich deshalb nicht auf eine bestimmte Reihenfolge. Beim Mischen ändert sich die Anordnung, nicht aber die Werte oder ihre Häufigkeit.

RandomNumberGenerator für sicherheitskritische Mischvorgänge verwenden

Wenn die Reihenfolge eine Sicherheitsentscheidung beeinflusst, sollten kryptografische Zufallsbytes die Grundlage für die Auswahlen von Fisher–Yates bilden. Auch die Umwandlung in einen begrenzten Wert muss unverzerrt sein: Wird eine Zufallszahl modulo der Grenze genommen, können manche Ergebnisse häufiger auftreten, wenn die Anzahl möglicher Zahlen nicht durch diese Grenze teilbar ist. Beim Rejection Sampling wird der kleine Überschussbereich verworfen, bevor der Rest berechnet wird.

Dieses vollständige Beispiel verwendet RandomNumberGenerator.Create() und dessen API GetBytes(byte[]), die ein Bytearray befüllt, und führt anschließend dieselbe absteigende Vertauschungsschleife aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

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));
    }
}

Die Schwellenwertberechnung verwirft Werte unterhalb der Grenze des größten durch die jeweilige Grenze teilbaren Bereichs. So wird ein Modulo-Bias für jede Grenze vermieden. RandomNumberGenerator macht die Auswahlen schwerer vorhersehbar; dadurch wird ein verzerrter Algorithmus nicht automatisch gleichverteilt und ein unsicheres Anwendungsdesign nicht sicher. Verwende diesen Generator nur, wenn Unvorhersehbarkeit wichtig ist, denn sein Aufwand ist höher als der von Random.

Warum OrderBy mit Random keine zuverlässige Mischmethode ist

Elemente nach erzeugten Zufallsschlüsseln zu sortieren ist nicht dasselbe, wie direkt aus dem verbleibenden Bereich auszuwählen und Werte zu vertauschen. Dabei wird tatsächlich sortiert, was im Allgemeinen mehr Arbeit erfordert als die lineare Schleife von Fisher–Yates. Außerdem können Random-Schlüssel gleich sein; die Reihenfolge solcher Elemente hängt dann vom Sortierverhalten ab. Für eine kurze Demonstration mag dieser Ansatz funktionieren, doch für eine gleichverteilte Permutation ist er nicht die bevorzugte Methode. Beim Fisher–Yates-Algorithmus sind die Auswahlen und die jeweils schrumpfenden Grenzen klar erkennbar.

Den passenden Ansatz auswählen

Verwende Fisher–Yates mit Random für gewöhnliche Mischvorgänge und denselben Algorithmus mit RandomNumberGenerator, wenn die Sicherheit von einer unvorhersehbaren Reihenfolge abhängt. In beiden Fällen sind unverzerrte begrenzte Zufallsauswahlen wichtig für ein gleichverteiltes Ergebnis. Verwende den Zufallszahlengenerator wieder, übergib das Array, das verändert werden soll, und beachte, dass sich die Reihenfolge bei jedem Durchlauf ändern kann. Vermeide das Sortieren nach Zufallsschlüsseln, wenn du eine klare, effiziente und gleichverteilte Mischmethode benötigst.