Il modo migliore per randomizzare un array con .NET

Question

Qual è il modo migliore per randomizzare un array di stringhe con .NET? Il mio array contiene circa 500 stringhe e vorrei creare un nuovo Array con le stesse stringhe ma in un ordine casuale.

Includi un esempio C # nella tua risposta.

Answer 1

Se sei su .NET 3.5, puoi usare il seguente cool di IEnumerable (VB.NET, non C #, ma l'idea dovrebbe essere chiara ...):

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

Modifica: OK ed ecco il codice VB.NET corrispondente:

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

Seconda modifica, in risposta alle osservazioni che System.Random "non è thread-safe" e "adatto solo per app giocattolo" a causa del ritorno di una sequenza basata sul tempo: come usato nel mio esempio, Random () è perfettamente thread-safe, a meno che non si consenta di inserire nuovamente la routine in cui si randomizza l'array, nel qual caso sarà necessario qualcosa come lock (MyRandomArray) per non corrompere i tuoi dati, che proteggerà anche rnd .

Inoltre, si dovrebbe capire che System.Random come fonte di entropia non è molto forte. Come indicato nella documentazione MSDN , è necessario utilizzare qualcosa derivato da System.Security.Cryptography.RandomNumberGenerator se stai facendo qualcosa relativo alla sicurezza. Ad esempio:

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

La seguente implementazione utilizza Algoritmo Fisher-Yates AKA Knuth Shuffle. Funziona in O (n) tempo e si mescola sul posto, quindi ha prestazioni migliori rispetto alla tecnica "ordina per casuale", sebbene sia più righe di codice. Vedi qui per alcune misurazioni comparative delle prestazioni. Ho usato System.Random, che va bene per scopi non crittografici. *

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

Utilizzo:

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

* Per array più lunghi, al fine di rendere altrettanto probabile il numero (estremamente elevato) di permutazioni, sarebbe necessario eseguire un generatore di numeri pseudo-casuale (PRNG) attraverso molte iterazioni per ogni scambio per produrre abbastanza entropia. Per un array di 500 elementi solo una minima parte dei 500 possibili! sarà possibile ottenere permutazioni usando un PRNG. Tuttavia, l'algoritmo Fisher-Yates è imparziale e quindi lo shuffle sarà buono quanto l'RNG che usi.

Answer 3

Stai cercando un algoritmo di mescolamento, giusto?

Ok, ci sono due modi per farlo: l'intelligente-ma-persone-sempre-sembrano-fraintendere-esso-e-sbagliare-così-forse-non-che-intelligente- dopotutto, e il modo stupido come scogli ma che importa se-perché-funziona.

Modo stupido

  

  
• Crea un duplicato del tuo primo array, ma tagga ogni stringa con un numero casuale.
  
• Ordina l'array duplicato rispetto al numero casuale.
  

Questo algoritmo funziona bene, ma assicurati che sia improbabile che il tuo generatore di numeri casuali tagghi due stringhe con lo stesso numero. A causa del cosiddetto Birthday Paradox , ciò accade più spesso di quanto ci si potrebbe aspettare. La sua complessità temporale è O ( n log n ).

Modo intelligente

Lo descriverò come un algoritmo ricorsivo:

  

Per mescolare un array di dimensioni n (indici nell'intervallo [0 .. n -1]):

     se n = 0      

  
• non fare nulla
  

     se n > 0      

  
• (passaggio ricorsivo) mescola i primi n -1 elementi dell'array
  
• scegli un indice casuale, x , nell'intervallo [0 .. n -1]
  
• scambia l'elemento all'indice n -1 con l'elemento all'indice x
  

L'equivalente iterativo è di guidare un iteratore attraverso l'array, scambiando con elementi casuali mentre procedi, ma nota che non puoi scambiare con un elemento dopo quello a cui punta l'iteratore. Questo è un errore molto comune e porta a uno shuffle di parte.

La complessità temporale è O ( n ).

Answer 4

Questo algoritmo è semplice ma non efficiente, O (N ² ). Tutto il " ordina per " gli algoritmi sono in genere O (N log N). Probabilmente non fa differenza al di sotto di centinaia di migliaia di elementi, ma sarebbe per elenchi di grandi dimensioni.

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

Il motivo per cui è O (N ² ) è sottile: List.RemoveAt () è un'operazione O (N) a meno che non venga rimossa in ordine dalla fine.

Answer 5

Puoi anche creare un metodo di estensione con Matt Howells. Esempio.

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

Quindi puoi semplicemente usarlo come:

        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

La randomizzazione dell'array è intensiva in quanto è necessario spostarsi su un gruppo di stringhe. Perché non leggere in modo casuale dall'array? Nel peggiore dei casi potresti persino creare una classe wrapper con getNextString (). Se hai davvero bisogno di creare un array casuale, allora potresti fare qualcosa del genere

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

Il * 5 è arbitrario.

Answer 7

Solo pensando dalla parte superiore della mia testa, potresti farlo:

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

Genera una matrice di float o ints casuali della stessa lunghezza. Ordina quell'array ed esegui gli swap corrispondenti sull'array di destinazione.

Questo produce un ordinamento veramente indipendente.

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, la tua soluzione è un IComparer personalizzato non è sicuro. Le routine di ordinamento richiedono che il comparatore sia conforme a diversi requisiti per funzionare correttamente. Il primo tra questi è la coerenza. Se il comparatore viene chiamato sulla stessa coppia di oggetti, deve sempre restituire lo stesso risultato. (il confronto deve anche essere transitivo).

Il mancato rispetto di questi requisiti può causare un numero qualsiasi di problemi nella routine di ordinamento, inclusa la possibilità di un ciclo infinito.

Per quanto riguarda le soluzioni che associano un valore numerico casuale a ciascuna voce e quindi ordinano in base a quel valore, queste comportano una propensione intrinseca nell'output poiché ogni volta che a due voci viene assegnato lo stesso valore numerico, la casualità dell'output essere compromesso. (In una routine di ordinamento "stabile", qualunque sia la prima nell'input sarà la prima nell'output. Array.Sort non sembra essere stabile, ma c'è ancora una distorsione basata sul partizionamento eseguito dall'algoritmo Quicksort) .

Devi pensare a quale livello di casualità hai bisogno. Se stai gestendo un sito di poker in cui hai bisogno di livelli crittografici di casualità per proteggerti da un determinato aggressore, hai requisiti molto diversi da qualcuno che vuole semplicemente randomizzare una playlist di brani.

Per la riproduzione casuale dell'elenco dei brani, non vi è alcun problema nell'utilizzo di un PRNG seed (come System.Random). Per un sito di poker, non è nemmeno un'opzione e devi pensare al problema molto più difficile di quanto chiunque farà per te su StackOverflow. (l'utilizzo di un RNG crittografico è solo l'inizio, è necessario assicurarsi che il proprio algoritmo non introduca una distorsione, che si disponga di sufficienti fonti di entropia e che non si esponga alcuno stato interno che possa compromettere la successiva casualità).

Answer 11

A questo post è già stata data una risposta abbastanza buona: usa un'implementazione di Durstenfeld del shuffle Fisher-Yates per un risultato rapido e imparziale. Sono state pubblicate anche alcune implementazioni, anche se noto che alcune sono in realtà errate.

Qualche tempo fa ho scritto un paio di post su implementando shuffles completi e parziali usando questa tecnica , e (questo secondo link è dove spero di aggiungere valore) anche un post di follow-up su come verificare se l'implementazione è imparziale , che può essere utilizzata per controllare qualsiasi algoritmo shuffle. Alla fine del secondo post puoi vedere l'effetto di un semplice errore nella selezione casuale dei numeri.

Answer 12

Ok, questo è chiaramente un bernoccolo dalla mia parte (mi scuso ...), ma uso spesso un metodo abbastanza generale e crittograficamente forte.

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 () è un'estensione su qualsiasi IEnumerable quindi ottenere, diciamo, numeri da 0 a 1000 in ordine casuale in un elenco può essere fatto con

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

Questo metodo non offre sorprese anche per quanto riguarda l'ordinamento, poiché il valore dell'ordinamento viene generato e ricordato esattamente una volta per elemento nella sequenza.

Answer 13

Non hai bisogno di algoritmi complicati.

Solo una linea semplice:

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

Nota che dobbiamo prima convertire Array in List , se non usi List in primo luogo.

Inoltre, tieni presente che questo non è efficace per array molto grandi! Altrimenti è pulito & amp; semplice.

Answer 14

Questa è una soluzione console funzionante completa basata su l'esempio fornito qui :

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

Questo codice mescola i numeri in un 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

Ecco un modo semplice con 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;
}