Najlepszy sposób na randomizację tablicy with.NET

Poniższa implementacja wykorzystuje algorytm Fisher-Yates . Działa w czasie O (n) i tasuje w miejscu, więc jest lepsza wydajność niż technika "Sortuj według losowości", chociaż jest więcej linii kodu. Zobacz TUTAJ dla niektórych porównawczych pomiarów wydajności. Użyłem systemu.Losowe, co jest dobre dla celów nie kryptograficznych.*

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

Użycie:

var array = new int[] {1, 2, 3, 4};
new Random().Shuffle(array);

* dla dłuższych tablic, aby (wyjątkowo duża) liczba permutacji była jednakowa prawdopodobnie konieczne byłoby uruchomienie generatora liczb pseudolosowych (PRNG) przez wiele iteracji dla każdego swapu, aby wytworzyć wystarczającą entropię. Dla 500-elementowej tablicy tylko bardzo mały ułamek z możliwych 500! permutacje będą możliwe do uzyskania za Pomocą PRNG. Niemniej jednak algorytm Fisher-Yates jest bezstronny i dlatego shuffle będzie tak samo dobry jak RNG, którego używasz.

Szukasz algorytmu tasowania, prawda?

Okay, są dwa sposoby, aby to zrobić: clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after- / align = "center" bgcolor = "# e0ffe0 " / premier Wysp Owczych / / align = center /

Dumb way

• Utwórz duplikat pierwszej tablicy, ale każdy łańcuch powinien być oznaczony losową liczbą.
• Sortuj duplikaty tablicy w odniesieniu do liczby losowej.

Ten algorytm działa dobrze, ale upewnij się, że generator liczb losowych jest mało prawdopodobne, aby oznaczyć dwa ciągi z tą samą liczbą. Ze względu na tak zwany paradoks urodzinowy zdarza się to częściej niż można się spodziewać. Jego złożoność czasowa wynosi O (N log n ).

Clever way

Opiszę to jako algorytm rekurencyjny:

Aby przetasować tablicę wielkości n (indeksy w zakresie [0..n-1]):

if n = 0

• nic nie rób

if n > 0

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

Odpowiednikiem iteracyjnym jest przejście iteratora przez tablicę, zwracając uwagę na to, że nie można zamienić elementu po elemencie, na który wskazuje iterator. Jest to bardzo częsty błąd i prowadzi do tendencyjnego przetasowania.

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

Ten algorytm jest prosty, ale nie wydajny, O (N²). Wszystkie algorytmy "order by" są zazwyczaj O (n log N). Prawdopodobnie nie robi różnicy poniżej setek tysięcy elementów, ale byłoby to dla 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);
}

The reason why it ' s O (N²) jest subtelna: lista.RemoveAt () jest operacją O (N), chyba że usuniesz w kolejności od końca.

Możesz również zrobić metodę rozszerzania 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;
                }
            }
        }
    }

Wtedy możesz 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>();

Randomizowanie tablicy jest intensywne, ponieważ musisz przesunąć kilka ciągów. Dlaczego nie po prostu przypadkowo odczytać z tablicy? W najgorszym przypadku można nawet utworzyć klasę wrappera za pomocą getNextString (). Jeśli naprawdę potrzebujesz utworzyć tablicę losową, możesz zrobić coś w stylu

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

*5 jest dowolne.

Tak sobie myślę, że mógłbyś to zrobić:

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

Ten post został już dość dobrze odpowiedział-użyj implementacji Durstenfeld shuffle Fisher-Yates dla szybkiego i bezstronnego wyniku. Były nawet niektóre implementacje opublikowane, choć zauważam, że niektóre są rzeczywiście nieprawidłowe.

Napisałem kilka postów jakiś czas temu o implementowaniu pełnych i częściowych tasowań przy użyciu tej techniki, i (ten drugi link jest tam, gdzie mam nadzieję dodać wartość) również kolejny post o tym, jak sprawdzić, czy Twoje implementacja jest bezstronna, która może być używana do sprawdzania dowolnego algorytmu shuffle. Możesz zobaczyć na końcu drugiego posta efekt prostego błędu w wyborze liczb losowych.

Wygeneruj tablicę losowych pływaków lub intów o tej samej długości. Posortuj tę tablicę i wykonaj odpowiednie swapy na tablicy docelowej.

Daje to 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, Twoim rozwiązaniem jest niestandardowy IComparer nie jest bezpieczny. Procedury sortowania wymagają, aby porównywarka spełniała kilka wymagań w celu prawidłowego działania. Pierwsza z nich to konsekwencja. Jeśli comparer jest wywoływany 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 spowodować wiele problemów w rutynie sortowania, w tym możliwość istnienia nieskończonej pętli.

Jeśli chodzi o rozwiązania, które wiążą losową wartość liczbową z każdym wpisem, a następnie sortują według tej wartości, prowadzą do nieodłącznego błędu na wyjściu, ponieważ za każdym razem, gdy dwa wpisy są przypisane tej samej wartości liczbowej, losowość wyjścia będzie zagrożona. (W" stabilnej " rutynie sortowania, która jest pierwsza na wejściu, będzie pierwsza na wyjściu. / Align = "left" / Sortowanie nie jest stabilne, ale nadal istnieje błąd oparty na partycjonowaniu wykonanym przez Quicksort algorytm).

Musisz trochę pomyśleć o tym, jakiego poziomu przypadkowości potrzebujesz. Jeśli prowadzisz witrynę pokerową, w której potrzebujesz kryptograficznych poziomów losowości, aby chronić się przed zdeterminowanym napastnikiem, masz bardzo różne wymagania od kogoś, kto chce po prostu losować listę utworów.

Do tasowania list piosenek, nie ma problemu z użyciem seeded PRNG (jak System.Random). Dla witryny pokerowej, to nawet nie jest opcja i trzeba myśleć o problemie a o wiele trudniej niż ktokolwiek inny zrobi dla Ciebie na stackoverflow. (użycie kryptograficznego RNG to dopiero początek, musisz upewnić się, że Twój algorytm nie wprowadzi błędu, że masz wystarczające źródła entropii i że nie ujawnisz żadnego stanu wewnętrznego, który zagroziłby późniejszej przypadkowości).

Ok, to ewidentnie wybój 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 dla dowolnej liczby, więc otrzymanie, powiedzmy, liczb od 0 do 1000 w losowej kolejności na liście może być wykonane za pomocą

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

Ta metoda również nie da ż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();

Zauważ, że musimy najpierw przekonwertować Array na List, jeśli nie użyjesz List w pierwszej kolejności.

Należy również pamiętać, że nie jest to efektywne dla bardzo dużych tablic! W przeciwnym razie jest czysty i prosty.

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

Ten kod tasuje liczby w tablicy.

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

Oto prosty sposób użycia 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;
}