Der beste Weg, um ein Array mit .NET zu randomisieren

Was ist der beste Weg, um ein Array von Zeichenfolgen mit .NET zu randomisieren? Mein Array enthält ungefähr 500 Zeichenfolgen und ich möchte eine neue Arraymit denselben Zeichenfolgen erstellen, jedoch in zufälliger Reihenfolge.

Bitte fügen Sie Ihrer Antwort ein C # -Beispiel bei.

Wenn Sie mit .NET 3.5 arbeiten, können Sie die folgende IEnumerable-Coolness verwenden (VB.NET, nicht C #, aber die Idee sollte klar sein ...):

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();    

Bearbeiten: OK und hier ist der entsprechende VB.NET-Code:

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()

Zweite Bearbeitung als Antwort auf die Bemerkung, dass System.Random aufgrund der Rückgabe einer zeitbasierten Sequenz "nicht threadsicher" und "nur für Spielzeug-Apps geeignet" ist: Wie in meinem Beispiel verwendet, ist Random () absolut threadsicher, es sei denn Sie lassen zu, dass die Routine, in der Sie das Array randomisieren, erneut eingegeben wird. In diesem Fall benötigen Sie lock (MyRandomArray)sowieso etwas , um Ihre Daten nicht zu beschädigen, was ebenfalls den Schutz schützt rnd.

Es sollte auch klar sein, dass System.Random als Entropiequelle nicht sehr stark ist. Wie in der MSDN-Dokumentation angegeben , sollten Sie etwas verwenden, das von abgeleitet ist, System.Security.Cryptography.RandomNumberGeneratorwenn Sie sicherheitsrelevante Maßnahmen ergreifen. Beispielsweise:

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

Die folgende Implementierung verwendet den Fisher-Yates-Algorithmus AKA the Knuth Shuffle. Es läuft in O (n) -Zeit und mischt an Ort und Stelle, ist also leistungsfähiger als die Technik "Nach Zufall sortieren", obwohl es sich um mehr Codezeilen handelt. Sehen Sie hier für einige vergleichende Leistungsmessungen. Ich habe System.Random verwendet, was für nicht kryptografische Zwecke in Ordnung ist. *

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

Verwendung:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* Für längere Arrays wäre es notwendig, einen Pseudozufallszahlengenerator (PRNG) durch viele Iterationen für jeden Swap zu führen, um die (extrem große) Anzahl von Permutationen gleich wahrscheinlich zu machen, um genügend Entropie zu erzeugen. Für ein 500-Elemente-Array nur ein sehr kleiner Bruchteil der möglichen 500! Permutationen können mit einem PRNG erhalten werden. Trotzdem ist der Fisher-Yates-Algorithmus unvoreingenommen und daher ist das Mischen so gut wie das von Ihnen verwendete RNG.

Sie suchen nach einem Mischalgorithmus, oder?

Okay, es gibt zwei Möglichkeiten, dies zu tun: Die Schlauen, aber die Leute scheinen es immer falsch zu verstehen und es falsch zu verstehen, also ist es vielleicht doch nicht so klug Weg, und der stumm wie Felsen, aber wen interessiert das, weil es funktioniert.

Blöder Weg

• Erstellen Sie ein Duplikat Ihres ersten Arrays, aber kennzeichnen Sie jede Zeichenfolge mit einer Zufallszahl.
• Sortieren Sie das doppelte Array in Bezug auf die Zufallszahl.

Dieser Algorithmus funktioniert gut, aber stellen Sie sicher, dass Ihr Zufallszahlengenerator wahrscheinlich nicht zwei Zeichenfolgen mit derselben Nummer markiert. Aufgrund des sogenannten Geburtstagsparadoxons geschieht dies häufiger als erwartet. Seine zeitliche Komplexität beträgt O ( n log n ).

Kluger Weg

Ich werde dies als rekursiven Algorithmus beschreiben:

So mischen Sie ein Array der Größe n (Indizes im Bereich [0 .. n -1]):

wenn n = 0

• nichts tun

wenn n > 0

• (rekursiver Schritt) Mische die ersten n -1 Elemente des Arrays
• wähle einen zufälligen Index x im Bereich [0 .. n -1]
• Tauschen Sie das Element am Index n -1 gegen das Element am Index x aus

Das iterative Äquivalent besteht darin, einen Iterator durch das Array zu führen und dabei mit zufälligen Elementen zu tauschen. Beachten Sie jedoch, dass Sie nicht mit einem Element nach dem Element tauschen können , auf das der Iterator zeigt. Dies ist ein sehr häufiger Fehler und führt zu einem voreingenommenen Shuffle.

Die zeitliche Komplexität ist O ( n ).

Dieser Algorithmus ist einfach, aber nicht effizient, O (N ² ). Alle "Order by" -Algorithmen sind typischerweise O (N log N). Unter Hunderttausenden von Elementen macht es wahrscheinlich keinen Unterschied, aber bei großen Listen.

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

Der Grund, warum es O (N ² ) ist, ist subtil: List.RemoveAt () ist eine O (N) -Operation, es sei denn, Sie entfernen in der Reihenfolge vom Ende.

Sie können auch eine Erweiterungsmethode aus Matt Howells erstellen. Beispiel.

   namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

Dann können Sie es einfach so verwenden:

        string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();

Das Randomisieren des Arrays ist intensiv, da Sie eine Reihe von Zeichenfolgen verschieben müssen. Warum nicht einfach zufällig aus dem Array lesen? Im schlimmsten Fall können Sie sogar eine Wrapper-Klasse mit getNextString () erstellen. Wenn Sie wirklich ein zufälliges Array erstellen müssen, können Sie so etwas tun

for i = 0 -> i= array.length * 5
   swap two strings in random places

Die * 5 ist beliebig.

Wenn Sie nur an meinen Kopf denken, können Sie dies tun:

public string[] Randomize(string[] input)
{
  List<string> inputList = input.ToList();
  string[] output = new string[input.Length];
  Random randomizer = new Random();
  int i = 0;

  while (inputList.Count > 0)
  {
    int index = r.Next(inputList.Count);
    output[i++] = inputList[index];
    inputList.RemoveAt(index);
  }

  return (output);
}

Generieren Sie ein Array von zufälligen Floats oder Ints gleicher Länge. Sortieren Sie dieses Array und führen Sie entsprechende Swaps für Ihr Zielarray durch.

Dies ergibt eine wirklich unabhängige Sorte.

Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();

while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}

Jacco, Ihre Lösung für einen benutzerdefinierten IComparer ist nicht sicher. Die Sortierroutinen erfordern, dass der Vergleicher mehrere Anforderungen erfüllt, um ordnungsgemäß zu funktionieren. An erster Stelle steht dabei die Konsistenz. Wenn der Vergleicher für dasselbe Objektpaar aufgerufen wird, muss er immer dasselbe Ergebnis zurückgeben. (Der Vergleich muss auch transitiv sein).

Die Nichterfüllung dieser Anforderungen kann zu einer Reihe von Problemen in der Sortierroutine führen, einschließlich der Möglichkeit einer Endlosschleife.

In Bezug auf die Lösungen, die jedem Eintrag einen zufälligen numerischen Wert zuordnen und dann nach diesem Wert sortieren, führen diese zu einer inhärenten Verzerrung in der Ausgabe, da jedes Mal, wenn zwei Einträgen der gleiche numerische Wert zugewiesen wird, die Zufälligkeit der Ausgabe beeinträchtigt wird. (In einer "stabilen" Sortierroutine ist das, was zuerst in der Eingabe steht, das erste in der Ausgabe. Array.Sort ist zwar nicht stabil, aber es gibt immer noch eine Verzerrung, die auf der vom Quicksort-Algorithmus vorgenommenen Partitionierung basiert.)

Sie müssen sich überlegen, welchen Grad an Zufälligkeit Sie benötigen. Wenn Sie eine Pokerseite betreiben, auf der Sie kryptografische Zufallsstufen benötigen, um sich vor einem entschlossenen Angreifer zu schützen, haben Sie ganz andere Anforderungen als jemand, der nur eine Song-Wiedergabeliste zufällig auswählen möchte.

Für das Mischen von Songlisten gibt es kein Problem mit einem gesetzten PRNG (wie System.Random). Für eine Pokerseite ist dies nicht einmal eine Option und Sie müssen viel schwieriger über das Problem nachdenken, als irgendjemand bei einem Stackoverflow für Sie tun wird. (Die Verwendung eines kryptografischen RNG ist nur der Anfang. Sie müssen sicherstellen, dass Ihr Algorithmus keine Verzerrung einführt, dass Sie über ausreichende Entropiequellen verfügen und dass Sie keinen internen Zustand offenlegen, der die nachfolgende Zufälligkeit beeinträchtigen würde.)

Dieser Beitrag wurde bereits ziemlich gut beantwortet - verwenden Sie eine Durstenfeld-Implementierung des Fisher-Yates-Shuffle für ein schnelles und unvoreingenommenes Ergebnis. Es wurden sogar einige Implementierungen veröffentlicht, obwohl ich feststelle, dass einige tatsächlich falsch sind.

Ich habe vor einiger Zeit einige Posts über die Implementierung von vollständigen und teilweisen Shuffles mit dieser Technik geschrieben und (über diesen zweiten Link möchte ich einen Mehrwert schaffen) auch einen Follow-up-Post darüber, wie Sie überprüfen können, ob Ihre Implementierung unvoreingenommen ist. Hiermit kann jeder Shuffle-Algorithmus überprüft werden. Sie können am Ende des zweiten Beitrags sehen, wie sich ein einfacher Fehler in der Zufallszahlenauswahl auswirken kann.

Ok, das ist eindeutig eine Beule von meiner Seite (entschuldigt sich ...), aber ich verwende oft eine ziemlich allgemeine und kryptografisch starke Methode.

public static class EnumerableExtensions
{
    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
    {
        var randomIntegerBuffer = new byte[4];
        Func<int> rand = () =>
                             {
                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);
                             };
        return from item in enumerable
               let rec = new {item, rnd = rand()}
               orderby rec.rnd
               select rec.item;
    }
}

Shuffle () ist eine Erweiterung für jede IEnumerable, mit der beispielsweise Zahlen von 0 bis 1000 in zufälliger Reihenfolge in einer Liste abgerufen werden können

Enumerable.Range(0,1000).Shuffle().ToList()

Diese Methode wird auch beim Sortieren keine Überraschungen bereiten, da der Sortierwert genau einmal pro Element in der Sequenz generiert und gespeichert wird.

Sie benötigen keine komplizierten Algorithmen.

Nur eine einfache Zeile:

Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

Beachten Sie, dass wir das Arrayin ein Listerstes konvertieren müssen , wenn Sie es überhaupt nicht verwenden List.

Beachten Sie auch, dass dies für sehr große Arrays nicht effizient ist! Ansonsten ist es sauber und einfach.

Dies ist eine vollständig funktionierende Konsolenlösung, die auf dem hier aufgeführten Beispiel basiert :

class Program
{
    static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };

    static void Main()
    {
        var result = Shuffle(words1);
        foreach (var i in result)
        {
            Console.Write(i + " ");
        }
        Console.ReadKey();
    }

   static string[] Shuffle(string[] wordArray) {
        Random random = new Random();
        for (int i = wordArray.Length - 1; i > 0; i--)
        {
            int swapIndex = random.Next(i + 1);
            string temp = wordArray[i];
            wordArray[i] = wordArray[swapIndex];
            wordArray[swapIndex] = temp;
        }
        return wordArray;
    }         
}

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        List<int> numList = new List<int>();
        numList.AddRange(numbers);

        Console.WriteLine("Original Order");
        for (int i = 0; i < numList.Count; i++)
        {
            Console.Write(String.Format("{0} ",numList[i]));
        }

        Random random = new Random();
        Console.WriteLine("\n\nRandom Order");
        for (int i = 0; i < numList.Capacity; i++)
        {
            int randomIndex = random.Next(numList.Count);
            Console.Write(String.Format("{0} ", numList[randomIndex]));
            numList.RemoveAt(randomIndex);
        }
        Console.ReadLine();

Hier ist eine einfache Möglichkeit, OLINQ zu verwenden:

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }  
    return sortedList;
}