List<T> zufällig ordnen

Question

Wie kann man am besten die Reihenfolge einer generischen Liste in C# zufällig durcheinanderbringen? Ich habe eine endliche Menge von 75 Zahlen in einer Liste, denen ich eine zufällige Reihenfolge zuweisen möchte, um sie für eine Lotterie-Anwendung zu ziehen.

Answer 1

Mischen Sie jede (I)List mit einer Erweiterungsmethode basierend auf dem Fisher-Yates shuffle:

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

Verwendung:

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

Der obige Code verwendet die stark kritisierte System.Random-Methode zur Auswahl von Austauschkandidaten. Es ist schnell, aber nicht so zufällig, wie es sein sollte. Wenn Sie eine bessere Qualität der Zufälligkeit in Ihren Mischungen benötigen, verwenden Sie den Zufallszahlengenerator in System.Security.Cryptography wie folgt:

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

Ein einfacher Vergleich ist verfügbar auf diesem Blog (WayBack Machine).

Bearbeitung: Seitdem ich diese Antwort vor ein paar Jahren geschrieben habe, haben viele Leute kommentiert oder mir geschrieben, um den großen dummen Fehler in meinem Vergleich herauszustellen. Sie haben natürlich recht. Es ist nichts falsch mit System.Random, wenn es auf die beabsichtigte Weise verwendet wird. In meinem ersten obigen Beispiel instantiiere ich die rng-Variable innerhalb der Shuffle-Methode, was Probleme verursacht, wenn die Methode wiederholt aufgerufen wird. Unten finden Sie ein korrigiertes Beispiel auf der Grundlage eines wirklich nützlichen Kommentars, den ich heute von @weston hier im SO erhalten habe.

Program.cs:

using System;
using System.Collections.Generic;
using System.Threading;

namespace SimpleLottery
{
  class Program
  {
    private static void Main(string[] args)
    {
      var zahlen = new List(Enumerable.Range(1, 75));
      zahlen.Shuffle();
      Console.WriteLine("Die Gewinnzahlen lauten: {0}", string.Join(",  ", zahlen.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;
      }
    }
  }
}

Answer 2

Wenn wir nur Elemente in einer völlig zufälligen Reihenfolge mischen müssen (nur um die Elemente in einer Liste zu mischen), ziehe ich diesen einfachen, aber effektiven Code vor, der Elemente nach der GUID ordnet ...

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

---

Wie von einigen Personen in den Kommentaren erwähnt wurde, sind GUIDs nicht garantiert zufällig, daher sollten wir stattdessen einen echten Zufallszahlengenerator verwenden:

private static Random rng = new Random();
...
var shuffledcards = cards.OrderBy(a => rng.Next()).ToList();

Answer 3

Ich bin ein wenig überrascht von all den umständlichen Versionen dieses einfachen Algorithmus hier. Fisher-Yates (oder Knuth shuffle) ist etwas knifflig, aber sehr kompakt. Warum ist es knifflig? Weil du darauf achten musst, ob dein Zufallszahlengenerator r(a,b) einen Wert zurückgibt, bei dem b inklusiv oder exklusiv ist. Ich habe auch die Wikipedia-Beschreibung bearbeitet, damit die Leute nicht blind dem Pseudocode dort folgen und schwer zu erkennende Fehler verursachen. Für .Net gibt Random.Next(a,b) eine Zahl exklusiv von b zurück, also ohne weiteres, hier ist wie es in C#/.Net implementiert werden kann:

public static void Shuffle(this IList list, Random rnd)
{
    for(var i=list.Count; i > 0; i--)
        list.Swap(0, rnd.Next(0, i));
}

public static void Swap(this IList list, int i, int j)
{
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

Versuche diesen Code.

Answer 4

Erweiterungsmethode für IEnumerable:

public static IEnumerable Zufällig(this IEnumerable quelle)
{
    Random rnd = new Random();
    return quelle.OrderBy((item) => rnd.Next());
}

Answer 5

Idee ist es, ein anonymes Objekt mit Element und zufälliger Reihenfolge zu erhalten und dann die Elemente nach dieser Reihenfolge neu zu ordnen und den Wert zurückzugeben:

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