Najlepszy sposób na losowanie tablicy w .NET

Jaki jest najlepszy sposób na losowanie tablicy ciągów w .NET? Moja tablica zawiera około 500 ciągów i chciałbym utworzyć nową Arrayz tymi samymi ciągami, ale w losowej kolejności.

W odpowiedzi uwzględnij przykład w języku C #.

Jeśli korzystasz z .NET 3.5, możesz użyć następującego chłodu IEnumerable (VB.NET, nie C #, ale pomysł powinien być jasny ...):

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

Edycja: OK, a oto odpowiedni kod VB.NET:

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

Druga edycja, w odpowiedzi na uwagi, że System.Random „nie jest bezpieczny wątkowo” i „nadaje się tylko do aplikacji zabawek” ze względu na zwracanie sekwencji opartej na czasie: w moim przykładzie Random () jest całkowicie bezpieczna dla wątków, chyba że pozwalasz na ponowne wprowadzenie procedury, w której losujesz tablicę, w takim przypadku będziesz potrzebować czegoś podobnego, lock (MyRandomArray)aby nie uszkodzić danych, co również będzie chronić rnd.

Należy również dobrze zrozumieć, że System.Random jako źródło entropii nie jest zbyt mocne. Jak wspomniano w dokumentacji MSDN , powinieneś używać czegoś pochodzącego z, System.Security.Cryptography.RandomNumberGeneratorjeśli robisz coś związanego z bezpieczeństwem. Na przykład:

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

Następująca implementacja używa algorytmu Fishera-Yatesa znanego również jako Shuffle Knutha. Działa w czasie O (n) i tasuje w miejscu, więc jest lepsza niż technika „sortowania losowo”, chociaż zawiera więcej linii kodu. Zobacz tutaj kilka porównawczych pomiarów wydajności. Użyłem System.Random, co jest dobre do celów innych niż kryptograficzne. *

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

Stosowanie:

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

* W przypadku dłuższych tablic, aby (bardzo duża) liczba permutacji była równie prawdopodobna, konieczne byłoby uruchomienie generatora liczb pseudolosowych (PRNG) przez wiele iteracji dla każdej zamiany, aby wytworzyć wystarczającą entropię. Dla tablicy 500-elementowej tylko bardzo mały ułamek możliwych 500! permutacje będzie można uzyskać za pomocą PRNG. Niemniej jednak algorytm Fishera-Yatesa jest bezstronny i dlatego tasowanie będzie tak dobre, jak RNG, którego używasz.

Szukasz algorytmu tasowania, prawda?

Okay, są na to dwa sposoby: sprytny-ale-ludzie-zawsze-wydają się-niezrozumieli-i-źle-zrozumieli-tak-może-to-nie-tak-sprytny-mimo wszystko sposób i sposób głupi-jak-skały-ale-kogo to obchodzi, ponieważ-działa.

Głupi sposób

• Utwórz kopię swojej pierwszej tablicy, ale oznacz każdy ciąg z losową liczbą.
• Sortuj zduplikowaną tablicę według liczby losowej.

Ten algorytm działa dobrze, ale upewnij się, że generator liczb losowych prawdopodobnie nie oznaczy dwóch ciągów tą samą liczbą. Z powodu tak zwanego Paradoksu Urodzinowego zdarza się to częściej, niż można by się spodziewać. Jego złożoność czasowa wynosi O ( n log n ).

Sprytny sposób

Opiszę to jako algorytm rekurencyjny:

Aby przetasować tablicę o rozmiarze n (indeksy w zakresie [0 .. n -1]):

jeśli n = 0

• nic nie robić

jeśli n > 0

• (krok rekurencyjny) tasuje pierwsze n- 1 elementy tablicy
• wybierz losowy indeks, x , z zakresu [0 .. n -1]
• zamień element o indeksie n -1 z elementem o indeksie x

Iteracyjnym odpowiednikiem jest przeprowadzenie iteratora po tablicy, zamieniając się losowymi elementami w trakcie, ale zauważ, że nie można zamienić elementu po tym, na który wskazuje iterator. Jest to bardzo częsty błąd i prowadzi do stronniczego tasowania.

Złożoność czasowa wynosi O ( n ).

Ten algorytm jest prosty, ale nie wydajny, O (N ² ). Wszystkie algorytmy „uporządkowane według” są zwykle O (N log N). Prawdopodobnie nie robi różnicy poniżej setek tysięcy elementów, ale miałoby to miejsce w przypadku dużych list.

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

Powód, dla którego to O (N ² ) jest subtelny: List.RemoveAt () jest operacją O (N), chyba że usuniesz w kolejności od końca.

Możesz także zrobić metodę rozszerzenia z Matta Howellsa. Przykład.

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

Następnie możesz po prostu użyć go tak:

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

Losowanie tablicy jest intensywne, ponieważ musisz zmieniać kilka ciągów. Dlaczego nie po prostu losowo odczytać z tablicy? W najgorszym przypadku możesz nawet utworzyć klasę opakowującą za pomocą metody getNextString (). Jeśli naprawdę potrzebujesz utworzyć losową tablicę, możesz zrobić coś takiego

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

* 5 jest arbitralne.

Po prostu myśląc z góry mojej głowy, możesz zrobić to:

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

Wygeneruj tablicę losowych liczb zmiennoprzecinkowych lub liczb całkowitych o tej samej długości. Posortuj tę tablicę i wykonaj odpowiednie zamiany na tablicy docelowej.

To daje prawdziwie niezależny rodzaj.

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, twoje rozwiązanie to niestandardowy IComparer nie jest bezpieczny. Procedury sortowania wymagają, aby funkcja porównująca spełniała kilka wymagań, aby działała poprawnie. Pierwsza z nich to konsekwencja. Jeśli funkcja porównująca jest wywoływana na tej samej parze obiektów, musi zawsze zwracać ten sam wynik. (porównanie musi być również przechodnie).

Niespełnienie tych wymagań może powodować wiele problemów w procedurze sortowania, w tym możliwość nieskończonej pętli.

Jeśli chodzi o rozwiązania, które kojarzą losową wartość liczbową z każdym wpisem, a następnie sortują je według tej wartości, prowadzą one do nieodłącznego odchylenia w wyniku, ponieważ za każdym razem, gdy dwóm wpisom zostanie przypisana ta sama wartość liczbowa, losowość wyniku będzie zagrożona. (W "stabilnej" procedurze sortowania, cokolwiek jest pierwsze na wejściu, będzie pierwsze w wyjściu. Array.Sort nie jest stabilne, ale nadal istnieje odchylenie oparte na partycjonowaniu wykonanym przez algorytm Quicksort).

Musisz trochę pomyśleć o tym, jakiego poziomu losowości potrzebujesz. Jeśli prowadzisz serwis pokerowy, w którym potrzebujesz kryptograficznych poziomów losowości, aby chronić się przed zdeterminowanym napastnikiem, masz bardzo inne wymagania niż ktoś, kto chce po prostu losować listę odtwarzania utworów.

W przypadku tasowania listy utworów nie ma problemu z używaniem rozstawionego PRNG (takiego jak System.Random). W przypadku strony pokerowej nie jest to nawet opcja i musisz pomyśleć o problemie dużo trudniej niż ktokolwiek ma zamiar zrobić dla ciebie w stackoverflow. (użycie kryptograficznego RNG to dopiero początek, musisz upewnić się, że twój algorytm nie wprowadza odchylenia, że ​​masz wystarczające źródła entropii i że nie ujawniasz żadnego stanu wewnętrznego, który zagrażałby późniejszej losowości).

Odpowiedzi na ten post są już całkiem dobre - użyj implementacji tasowania Fisher-Yatesa Durstenfelda, aby uzyskać szybki i obiektywny wynik. Opublikowano nawet kilka implementacji, chociaż zauważam, że niektóre są w rzeczywistości niepoprawne.

Niedawno napisałem kilka postów na temat implementacji pełnego i częściowego tasowania przy użyciu tej techniki , a (mam nadzieję, że dodam wartość w tym drugim linku), także post o tym, jak sprawdzić, czy Twoja implementacja jest bezstronna , które można wykorzystać do sprawdzenia dowolnego algorytmu tasowania. Na końcu drugiego postu widać efekt prostego błędu w wyborze liczb losowych.

Ok, to ewidentnie uderzenie z mojej strony (przeprasza ...), ale często używam dość ogólnej i silnej kryptograficznie metody.

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 () jest rozszerzeniem dowolnego IEnumerable, więc na przykład pobieranie liczb od 0 do 1000 w kolejności losowej na liście można wykonać za pomocą

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

Ta metoda również nie sprawi żadnych niespodzianek, jeśli chodzi o sortowanie, ponieważ wartość sortowania jest generowana i zapamiętywana dokładnie raz na element w sekwencji.

Nie potrzebujesz skomplikowanych algorytmów.

Tylko jedna prosta linia:

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

Należy pamiętać, że musimy przekonwertować ArrayDo Listpierwszego, jeśli nie korzystają Listw pierwszej kolejności.

Pamiętaj też, że nie jest to wydajne w przypadku bardzo dużych tablic! W przeciwnym razie jest to czyste i proste.

To jest kompletne działające rozwiązanie konsoli oparte na przykładzie podanym tutaj :

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

Oto prosty sposób korzystania z 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);

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