Randomizza una lista

Qual è il modo migliore per randomizzare l’ordine di un elenco generico in C #? Ho un insieme finito di 75 numeri in una lista a cui vorrei assegnare un ordine casuale, per disegnarli per un’applicazione tipo lotteria.

    Mescola qualsiasi (I)List con un metodo di estensione basato sul rimescolamento di Fisher-Yates :

     private static Random rng = new Random(); public static void Shuffle(this IList list) { int n = list.Count; while (n > 1) { n--; int k = rng.Next(n + 1); T value = list[k]; list[k] = list[n]; list[n] = value; } } 

    Uso:

     List products = GetProducts(); products.Shuffle(); 

    Il codice sopra utilizza il metodo System.Random molto criticato per selezionare i candidati di scambio. È veloce ma non casuale come dovrebbe essere. Se hai bisogno di una migliore qualità della casualità nello shuffle usa il generatore di numeri casuali in System.Security.Cryptography in questo modo:

     using System.Security.Cryptography; ... public static void Shuffle(this IList list) { RNGCryptoServiceProvider provider = new RNGCryptoServiceProvider(); int n = list.Count; while (n > 1) { byte[] box = new byte[1]; do provider.GetBytes(box); while (!(box[0] < n * (Byte.MaxValue / n))); int k = (box[0] % n); n--; T value = list[k]; list[k] = list[n]; list[n] = value; } } 

    Un semplice confronto è disponibile su questo blog (WayBack Machine).

    Edit: Da quando ho scritto questa risposta un paio di anni fa, molte persone mi hanno commentato o scritto, per sottolineare il grande errore sciocco nel mio confronto. Ovviamente sono giusti. Non c'è niente di sbagliato in System.Random se è usato nel modo in cui è stato previsto. Nel mio primo esempio sopra, istanzio la variabile rng all'interno del metodo Shuffle, che sta cercando problemi se il metodo verrà chiamato ripetutamente. Di seguito è riportato un esempio completo e completo basato su un commento veramente utile ricevuto oggi da @weston qui su SO.

    Program.cs:

     using System; using System.Collections.Generic; using System.Threading; namespace SimpleLottery { class Program { private static void Main(string[] args) { var numbers = new List(Enumerable.Range(1, 75)); numbers.Shuffle(); Console.WriteLine("The winning numbers are: {0}", string.Join(", ", numbers.GetRange(0, 5))); } } public static class ThreadSafeRandom { [ThreadStatic] private static Random Local; public static Random ThisThreadsRandom { get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + Thread.CurrentThread.ManagedThreadId))); } } } static class MyExtensions { public static void Shuffle(this IList list) { int n = list.Count; while (n > 1) { n--; int k = ThreadSafeRandom.ThisThreadsRandom.Next(n + 1); T value = list[k]; list[k] = list[n]; list[n] = value; } } } } 

    Se abbiamo solo bisogno di mischiare gli oggetti in un ordine completamente casuale (solo per mescolare gli elementi in una lista), preferisco questo codice semplice ma efficace che ordina gli oggetti per guid …

     var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList(); 

    Sono un po ‘sorpreso da tutte le versioni goffe di questo semplice algoritmo qui. Fisher-Yates (o Knuth shuffle) è un po ‘complicato ma molto compatto. Se vai su Wikipedia, vedresti una versione di questo algoritmo che ha il ciclo inverso al contrario e molte persone non sembrano davvero capire perché è al contrario. Il motivo principale è che questa versione dell’algoritmo presuppone che il generatore di numeri casuali Random(n) a tua disposizione abbia due proprietà seguenti:

    1. Accetta n come parametro di input singolo.
    2. Restituisce il numero da 0 a n incluso .

    Tuttavia, il generatore di numeri casuali .Net non soddisfa la proprietà # 2. Il Random.Next(n) restituisce invece il numero da 0 a n-1 incluso. Se si tenta di utilizzare il ciclo for al contrario, sarà necessario chiamare Random.Next(n+1) che aggiunge un’operazione aggiuntiva.

    Tuttavia, il generatore di numeri casuali .Net ha un’altra bella funzione Random.Next(a,b) che restituisce da a a b-1 inclusive. Questo in realtà si adatta perfettamente con l’implementazione di questo algoritmo che ha un normale ciclo. Quindi, senza ulteriori indugi, ecco l’implementazione corretta, efficiente e compatta:

     public static void Shuffle(this IList list, Random rnd) { for(var i=0; i < list.Count; i++) list.Swap(i, rnd.Next(i, list.Count)); } public static void Swap(this IList list, int i, int j) { var temp = list[i]; list[i] = list[j]; list[j] = temp; } 

    Metodo di estensione per IEnumerable:

     public static IEnumerable Randomize(this IEnumerable source) { Random rnd = new Random(); return source.OrderBy((item) => rnd.Next()); } 
      public static List Randomize(List list) { List randomizedList = new List(); Random rnd = new Random(); while (list.Count > 0) { int index = rnd.Next(0, list.Count); //pick a random item from the master list randomizedList.Add(list[index]); //place it at the end of the randomized list list.RemoveAt(index); } return randomizedList; } 

    EDIT Il RemoveAt è un punto debole nella mia versione precedente. Questa soluzione lo supera.

     public static IEnumerable Shuffle( this IEnumerable source, Random generator = null) { if (generator == null) { generator = new Random(); } var elements = source.ToArray(); for (var i = elements.Length - 1; i >= 0; i--) { var swapIndex = generator.Next(i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; } } 

    Nota il Random generator opzionale, se l’implementazione del framework di base di Random non è thread-safe o crittograficamente abbastanza forte per le tue esigenze, puoi iniettare la tua implementazione nell’operazione.

    In questa risposta è ansible trovare un’implementazione adatta per un’implementazione Random crittografia sicura per il thread.


    Ecco un’idea, estendi IList in un (si spera) modo efficace.

     public static IEnumerable Shuffle(this IList list) { var choices = Enumerable.Range(0, list.Count).ToList(); var rng = new Random(); for(int n = choices.Count; n > 1; n--) { int k = rng.Next(n); yield return list[choices[k]]; choices.RemoveAt(k); } yield return list[choices[0]]; } 

    È ansible farlo utilizzando questo semplice metodo di estensione

     public static class IEnumerableExtensions { public static IEnumerable Randomize(this IEnumerable target) { Random r = new Random(); return target.OrderBy(x=>(r.Next())); } } 

    e puoi usarlo facendo quanto segue

     // use this on any collection that implements IEnumerable! // List, Array, HashSet, Collection, etc List myList = new List { "hello", "random", "world", "foo", "bar", "bat", "baz" }; foreach (string s in myList.Randomize()) { Console.WriteLine(s); } 

    Io di solito uso:

     var list = new List (); fillList (list); var randomizedList = new List (); var rnd = new Random (); while (list.Count != 0) { var index = rnd.Next (0, list.Count); randomizedList.Add (list [index]); list.RemoveAt (index); } 

    Se si dispone di un numero fisso (75), è ansible creare un array con 75 elementi, quindi enumerare l’elenco, spostando gli elementi in posizioni casuali nell’array. È ansible generare la mapping del numero di elenco all’indice di matrice utilizzando il rimescolamento di Fisher-Yates .

    Questo è il mio metodo preferito di shuffle quando è desiderabile non modificare l’originale. È una variante dell’algoritmo “inside-out” di Fisher-Yates che funziona su qualsiasi sequenza enumerabile (la lunghezza della source non deve essere nota dall’inizio).

     public static IList NextList(this Random r, IEnumerable source) { var list = new List(); foreach (var item in source) { var i = r.Next(list.Count + 1); if (i == list.Count) { list.Add(item); } else { var temp = list[i]; list[i] = item; list.Add(temp); } } return list; } 

    Questo algoritmo può anche essere implementato allocando un intervallo da 0 a length - 1 e estrapolando in modo casuale gli indici scambiando l’indice scelto a caso con l’ultimo indice fino a quando tutti gli indici sono stati scelti esattamente una volta. Questo codice sopra compie esattamente la stessa cosa ma senza l’allocazione aggiuntiva. Che è molto carino

    Per quanto riguarda la class Random , è un generatore di numeri generico (e se avessi una lotteria, considererei l’utilizzo di qualcosa di diverso). Inoltre, si basa su un valore di seme basato sul tempo per impostazione predefinita. Una piccola riduzione del problema è di seminare la class Random con RNGCryptoServiceProvider o si potrebbe usare RNGCryptoServiceProvider in un metodo simile a questo (vedi sotto) per generare valori di virgola mobile in virgola mobile casualmente scelti, ma eseguire una lotteria richiede molto la casualità e la natura della fonte della casualità.

     var bytes = new byte[8]; _secureRng.GetBytes(bytes); var v = BitConverter.ToUInt64(bytes, 0); return (double)v / ((double)ulong.MaxValue + 1); 

    Il punto di generare un doppio casuale (tra 0 e 1 esclusivamente) deve essere utilizzato per ridimensionare a una soluzione intera. Se devi scegliere qualcosa da un elenco basato su una doppia x casuale che sarà sempre 0 < = x && x < 1 è semplice.

     return list[(int)(x * list.Count)]; 

    Godere!

    Se non ti dispiace usare due Lists , probabilmente questo è il modo più semplice per farlo, ma probabilmente non è il più efficiente o imprevedibile:

     List xList = new List() { 1, 2, 3, 4, 5 }; List deck = new List(); foreach (int xInt in xList) deck.Insert(random.Next(0, deck.Count + 1), xInt); 

    Ecco un efficiente Shuffler che restituisce una serie di byte di valori mescolati. Non rimescola mai più del necessario. Può essere riavviato da dove era stato interrotto in precedenza. La mia effettiva implementazione (non mostrata) è un componente MEF che consente un shuffler di sostituzione specificato dall’utente.

      public byte[] Shuffle(byte[] array, int start, int count) { int n = array.Length - start; byte[] shuffled = new byte[count]; for(int i = 0; i < count; i++, start++) { int k = UniformRandomGenerator.Next(n--) + start; shuffled[i] = array[k]; array[k] = array[start]; array[start] = shuffled[i]; } return shuffled; } 

    `

      public Deck(IEnumerable initialCards) { cards = new List(initialCards); public void Shuffle() } { List NewCards = new List(); while (cards.Count > 0) { int CardToMove = random.Next(cards.Count); NewCards.Add(cards[CardToMove]); cards.RemoveAt(CardToMove); } cards = NewCards; } public IEnumerable GetCardNames() { string[] CardNames = new string[cards.Count]; for (int i = 0; i < cards.Count; i++) CardNames[i] = cards[i].Name; return CardNames; } Deck deck1; Deck deck2; Random random = new Random(); public Form1() { InitializeComponent(); ResetDeck(1); ResetDeck(2); RedrawDeck(1); RedrawDeck(2); } private void ResetDeck(int deckNumber) { if (deckNumber == 1) { int numberOfCards = random.Next(1, 11); deck1 = new Deck(new Card[] { }); for (int i = 0; i < numberOfCards; i++) deck1.Add(new Card((Suits)random.Next(4),(Values)random.Next(1, 14))); deck1.Sort(); } else deck2 = new Deck(); } private void reset1_Click(object sender, EventArgs e) { ResetDeck(1); RedrawDeck(1); } private void shuffle1_Click(object sender, EventArgs e) { deck1.Shuffle(); RedrawDeck(1); } private void moveToDeck1_Click(object sender, EventArgs e) { if (listBox2.SelectedIndex >= 0) if (deck2.Count > 0) { deck1.Add(deck2.Deal(listBox2.SelectedIndex)); } RedrawDeck(1); RedrawDeck(2); } 

    Ecco un modo thread-safe per fare questo:

     public static class EnumerableExtension { private static Random globalRng = new Random(); [ThreadStatic] private static Random _rng; private static Random rng { get { if (_rng == null) { int seed; lock (globalRng) { seed = globalRng.Next(); } _rng = new Random(seed); } return _rng; } } public static IEnumerable Shuffle(this IEnumerable items) { return items.OrderBy (i => rng.Next()); } } 

    Una semplice modifica della risposta accettata che restituisce una nuova lista invece di lavorare sul posto e accetta il più generale IEnumerable come fanno molti altri metodi Linq.

     private static Random rng = new Random(); ///  /// Returns a new list where the elements are randomly shuffled. /// Based on the Fisher-Yates shuffle, which has O(n) complexity. ///  public static IEnumerable Shuffle(this IEnumerable list) { var source = list.ToList(); int n = source.Count; var shuffled = new List(n); shuffled.AddRange(source); while (n > 1) { n--; int k = rng.Next(n + 1); T value = shuffled[k]; shuffled[k] = shuffled[n]; shuffled[n] = value; } return shuffled; } 

    L’idea è ottenere object anonimo con l’articolo e l’ordine casuale e quindi riordinare gli articoli con questo ordine e restituire il valore:

     var result = items.Select(x => new { value = x, order = rnd.Next() }) .OrderBy(x => x.order).Select(x => x.value).ToList() 

    Vecchio post di sicuro, ma io uso solo un GUID.

     Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList(); 

    Un GUID è sempre univoco e poiché viene rigenerato ogni volta che il risultato cambia ogni volta.

    Un approccio molto semplice a questo tipo di problema consiste nell’usare un numero di scambio di elementi casuali nell’elenco.

    In pseudo-codice questo dovrebbe assomigliare a questo:

     do r1 = randomPositionInList() r2 = randomPositionInList() swap elements at index r1 and index r2 for a certain number of times