Der beste Weg, ein Array mit .NET zufällig zu sortieren

Question

Was ist der beste Weg, ein Array von Zeichenfolgen mit .NET zufällig zu sortieren?Mein Array enthält etwa 500 Zeichenfolgen und ich möchte eine neue erstellen Array mit den gleichen Zeichenfolgen, aber in zufälliger Reihenfolge.

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

Answer 1

Wenn Sie .NET 3.5 verwenden, 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 Änderung 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 Thread-sicher, es sei denn, Sie lassen zu, dass die Routine, in der Sie das Array randomisieren, erneut eingegeben wird. In diesem Fall benötigen Sie so etwas wie lock (MyRandomArray) Auf jeden Fall, um Ihre Daten nicht zu beschädigen, was den Schutz gewährleistet rnd sowie.

Außerdem sollte klar sein, dass System.Random als Entropiequelle nicht sehr stark ist.Wie in der erwähnt MSDN-Dokumentation, sollten Sie etwas verwenden, das von abgeleitet ist System.Security.Cryptography.RandomNumberGenerator wenn Sie sicherheitsrelevante Maßnahmen ergreifen.Zum Beispiel:

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

Answer 2

Die folgende Implementierung verwendet das Fisher-Yates-Algorithmus AKA die Knuth Shuffle. Es läuft in O (n) Zeit und mischt vorhanden, so ist eine bessere Leistung als die ‚Sort by random‘ Technik, obwohl es mehr Codezeilen ist. Siehe hier für einige vergleichende Leistungsmessungen. Ich habe verwendet System.Random, die für nicht-kryptographische 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;
        }
    }
}

Verbrauch:

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, um die (extrem große) Anzahl von Permutationen gleich wahrscheinlich wäre es notwendig, um einen Pseudo-Zufallszahlengenerator (PRNG) durch viele Iterationen zu laufen für jede Swap genug Entropie zu produzieren. Für eine 500-Element-Array nur ein sehr kleiner Bruchteil der möglichen 500! Permutationen möglich sein wird, einen PRNG zu erhalten verwenden. Dennoch ist der Fisher-Yates-Algorithmus unvoreingenommen und deshalb wird der Shuffle so gut sein wie die RNG Sie verwenden.

Answer 3

Sie suchen nach einem Misch-Algorithmus, nicht wahr?

Okay, gibt es zwei Möglichkeiten, dies zu tun: die cleveren-but-Menschen-immer-scheinen zu mißverstehen-it-and-get-it-falsch-so-vielleicht-its-not-that-clever- nach-all Art und Weise, und die stummen-as-Felsen-aber-die-cares-da-it-Werk-Weg.

Dumb Weg

  

  
• Erstellen Sie eine Kopie Ihrer ersten Array, aber jede Saite Tag sollte mit einer Zufallszahl.
  
• Sortieren Sie die doppelte Anordnung in Bezug auf die Zufallszahl.
  

Dieser Algorithmus funktioniert gut, aber stellen Sie sicher, dass Ihr Zufallszahlengenerator ist unwahrscheinlich, dass zwei Strings mit der gleichen Nummer zu markieren. Wegen des sogenannten Geburtstag Paradox , geschieht dies öfter, als man erwarten könnte. Seine Zeit Komplexität ist O ( n log n ).

Clever Weg

Ich werde beschreiben, dies als ein rekursive Algorithmus:

  

eine Reihe von Größe So mischte n (Indizes im Bereich [0 .. n -1]):

     wenn n = 0      

  
• nichts tun
  

     wenn n > 0      

  
• (rekursive Schritt) mische das erste n -1 Elemente des Arrays
  
• Wählen Sie eine zufällige Index x , im Bereich [0 .. n -1]
  
• tauschen Sie das Element bei Index n -1 mit dem Element bei Index x
  

Die iterative äquivalent ist ein Iterator durch das Feld zu gehen, tauscht mit zufälligen Elementen, wie Sie gehen, aber feststellen, dass Sie nicht mit einem Elemente tauschen nach derjenige, der der Iterator verweist. Dies ist ein sehr häufiger Fehler, und führt zu einer verzerrten shuffle.

Zeitkomplexität O ( n ).

Answer 4

Dieser Algorithmus ist einfach, aber nicht effizient, O (N ² ). Alle "order by" Algorithmen sind in der Regel O (N log N). Es ist wahrscheinlich kein Unterschied unter Hunderttausenden von Elementen machen, aber es würde für große 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 ist O (N ² ) ist subtil: List.RemoveAt () ist ein O (N) Betrieb, wenn Sie, um vom Ende entfernen.

Answer 5

Sie können auch eine Erweiterung Methode aus Matt Howells machen. 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 einfach verwenden Sie es mögen:

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

Answer 6

das Array Randomisierung ist intensiv, wie Sie eine Reihe von Zeichenketten zu verschieben um sich zu haben. Warum nicht einfach zufällig aus dem Array gelesen hat? Im schlimmsten Fall könnte man sogar eine Wrapper-Klasse mit einem getNextString erstellen (). Wenn Sie wirklich ein zufälliges Array zu erstellen brauchen, dann können Sie etwas tun, wie

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

Die * 5 ist beliebig.

Answer 7

Sie einfach die Spitze von meinem Kopf dachte einmal, Sie könnten 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);
}

Answer 8

generiert eine Reihe von zufälligen Schwimmern oder Ints von gleicher Länge. Sortieren, dass Array und tun entsprechende Swaps auf Ihrem Ziel-Array.

Dies ergibt eine wirklich unabhängige Art.

Answer 9

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

Answer 10

Jacco, Ihre Lösung eines benutzerdefinierten IComparer ising ist nicht sicher. Die Sortierung Routinen erfordern die comparer auf mehrere Anforderungen anzupassen, um richtig zu funktionieren. An erster Stelle ist die Konsistenz. Wenn der Vergleich auf dem gleichen Paar von Objekten aufgerufen wird, muss es immer das gleiche Ergebnis zurück. (Der Vergleich muss auch transitiv sein).

Wenn Sie diese Anforderungen erfüllen kann eine beliebige Anzahl von Problemen in der Sortierroutine verursacht die Möglichkeit einer Endlosschleife einschließlich.

In Bezug auf den Lösungen, die einen Zufallszahlenwert mit jedem Eintrag zugeordnet wird und dann sortiert nach diesem Wert, so werden diese zu einer inhärenten Vorspannung in der Ausgangsleitung, da jederzeit zwei Einträge den gleichen numerischen Wert zugeordnet sind, die Zufälligkeit der Ausgabe wird kompromittiert. (In einer „stabilen“ Sortierroutine, je nachdem was zuerst in dem Eingang ist in der Ausgabe zuerst sein. Array.Sort geschieht nicht stabil sein, aber es ist immer noch eine Vorspannung auf der Grundlage der Partitionierung durch den Algorithmus Quicksort getan).

Sie müssen einige Denken tun über das, was Maß an Zufälligkeit Sie benötigen. Wenn Sie eine Poker-Site ausgeführt wird, wo Sie Verschlüsselungsebene Zufälligkeit müssen gegen einen entschlossenen Angreifer zu schützen, haben Sie sehr unterschiedliche Anforderungen von jemandem, der will nur einen Song Play randomisieren.

Für Song-Liste schlurfenden, gibt es kein Problem, eine entkernt PRNG mit (wie System.Random). Für eine Poker-Website, es ist nicht einmal eine Option, und Sie müssen über das Problem denken, viel härter als jeder andere für Sie auf Stackoverflow tun wird. (Ein kryptographisches RNG verwendet, ist nur der Anfang, müssen Sie sicherstellen, dass Ihr Algorithmus keinen Bias einführen, dass Sie über ausreichende Quellen der Entropie haben, und dass Sie nicht aussetzen keinen internen Zustand, die spätere Zufälligkeit gefährden würde).

Answer 11

Dieser Beitrag wird bereits ziemlich gut beantwortet worden - verwenden, um eine Durstenfeld Umsetzung des Fisher-Yates Shuffle für ein schnelles und unvoreingenommenes Ergebnis. Es gab sogar einige Implementierungen geschrieben, obwohl ich einige beachten sind eigentlich falsch.

Ich schrieb vor einiger Zeit über ein paar Beiträge eine Follow-up-Post über wie Sie überprüfen, ob Ihre Implementierung unvoreingenommene ist, die dazu verwendet werden können jeden Shuffle-Algorithmus zu überprüfen. Sie können in der Zufallszahl-Auswahl die Wirkung eines einfachen Fehlers am Ende des zweiten Stiels sehen machen kann.

Answer 12

Ok, das ist eindeutig eine Beule von meiner Seite (entschuldigt ...), aber ich benutze oft eine ganz allgemeine und kryptographisch 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 auf jedem IEnumerable so bekommen, sagen sie, Zahlen von 0 bis 1000 in zufälliger Reihenfolge in einer Liste kann mit

erfolgen

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

Dieses Verfahren macht auch pflegen Überraschungen, wenn es um das Sortieren kommt, da der Sortierwert erzeugt wird, und genau einmal pro Element in der Folge in Erinnerung.

Answer 13

Sie haben keine komplizierten Algorithmen benötigen.

Nur eine einfache Linie:

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

Beachten Sie, dass wir die Array zu einem List konvertieren müssen zuerst, wenn Sie nicht List in erster Linie verwendet werden.

Auch daran, dass dies für sehr großen Arrays nicht effizient ist! Ansonsten ist es sauber und einfach.

Answer 14

Dies ist eine komplette Arbeits Console Lösung basierend auf das Beispiel hier vorgesehen :

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

Answer 15

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

Answer 16

Dieser Code schlurft Zahlen in einem Array.

using System;

// ...
    static void Main(string[] args)
    {
        Console.ForegroundColor = ConsoleColor.Cyan;
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Shuffle(numbers);

        for (int i = 0; i < numbers.Length; i++)
            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
        Console.WriteLine();

        string[] words = { "this", "is", "a", "string", "of", "words" };
        Shuffle(words);

        for (int i = 0; i < words.Length; i++)
            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
        Console.WriteLine();

        Console.ForegroundColor = ConsoleColor.Gray;
        Console.Write("Press any key to quit . . . ");
        Console.ReadKey(true);
    }

    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();

        for (int i = 0; i < array.Length; i++)
        {
            T temporary = array[i];
            int intrandom = random.Next(array.Length);
            array[i] = array[intrandom];
            array[intrandom] = temporary;
        }
    }

Answer 17

Hier ist eine einfache Art und Weise mit OLINQ:

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

Answer 18

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