Randomisieren Sie eine Liste <T>

Was ist der beste Weg, um die Reihenfolge einer generischen Liste in C # zufällig zu bestimmen? Ich habe einen endlichen Satz von 75 Zahlen in einer Liste, der ich eine zufällige Reihenfolge zuweisen möchte, um sie für eine Lotterieanwendung zu zeichnen.

Mische alle (I)Listmit einer Erweiterungsmethode, die auf dem Fisher-Yates-Shuffle basiert :

private static Random rng = new Random();  

public static void Shuffle<T>(this IList<T> 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;  
    }  
}

Verwendungszweck:

List<Product> products = GetProducts();
products.Shuffle();

Der obige Code verwendet die viel kritisierte System.Random-Methode, um Swap-Kandidaten auszuwählen. Es ist schnell, aber nicht so zufällig, wie es sein sollte. Wenn Sie eine bessere Qualität der Zufälligkeit in Ihren Mischvorgängen benötigen, verwenden Sie den Zufallszahlengenerator in System.Security.Cryptography wie folgt:

using System.Security.Cryptography;
...
public static void Shuffle<T>(this IList<T> 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 in diesem Blog (WayBack Machine) verfügbar .

Bearbeiten: Seit ich diese Antwort vor ein paar Jahren geschrieben habe, haben viele Leute mich kommentiert oder geschrieben, um auf den großen dummen Fehler in meinem Vergleich hinzuweisen. Sie haben natürlich recht. Es ist nichts falsch mit System.Random, wenn es so verwendet wird, wie es beabsichtigt war. In meinem ersten Beispiel oben instanziiere ich die Variable rng innerhalb der Shuffle-Methode, die nach Problemen fragt, wenn die Methode wiederholt aufgerufen werden soll. Unten finden Sie ein festes, vollständiges Beispiel, das auf einem wirklich nützlichen Kommentar basiert, den @weston heute hier auf SO erhalten hat.

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<int>(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<T>(this IList<T> 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;
      }
    }
  }
}

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

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

Ich bin etwas überrascht von all den klobigen Versionen dieses einfachen Algorithmus hier. Fisher-Yates (oder Knuth Shuffle) ist etwas knifflig, aber sehr kompakt. Warum ist es schwierig? Weil Sie darauf achten müssen, ob Ihr Zufallszahlengenerator einen r(a,b)Wert zurückgibt, der binklusive oder exklusiv ist. Ich habe auch die Wikipedia-Beschreibung bearbeitet, damit die Leute dort nicht blindlings dem Pseudocode folgen und schwer zu erkennende Fehler erstellen. Gibt für .Net ohne weiteres eine Random.Next(a,b)exklusive Nummer bzurück. So kann es in C # /. Net implementiert werden:

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

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

Versuchen Sie diesen Code .

Erweiterungsmethode für IEnumerable:

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}

Die Idee ist, ein anonymes Objekt mit Artikel und zufälliger Reihenfolge zu erhalten und die Artikel dann nach dieser Reihenfolge und dem Rückgabewert neu zu ordnen:

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

    public static List<T> Randomize<T>(List<T> list)
    {
        List<T> randomizedList = new List<T>();
        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;
    }

BEARBEITEN Das RemoveAtist eine Schwäche in meiner vorherigen Version. Diese Lösung überwindet das.

public static IEnumerable<T> Shuffle<T>(
        this IEnumerable<T> 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];
    }
}

Beachten Sie die Option Random generator: Wenn die Basis-Framework-Implementierung von Randomnicht threadsicher oder kryptografisch stark genug für Ihre Anforderungen ist, können Sie Ihre Implementierung in den Vorgang einfügen.

Eine geeignete Implementierung für eine thread-sichere kryptografisch starke RandomImplementierung finden Sie in dieser Antwort.

Hier ist eine Idee, IList auf (hoffentlich) effiziente Weise zu erweitern.

public static IEnumerable<T> Shuffle<T>(this IList<T> 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]];
}

Sie können dies mit dieser einfachen Erweiterungsmethode erreichen

public static class IEnumerableExtensions
{

    public static IEnumerable<t> Randomize<t>(this IEnumerable<t> target)
    {
        Random r = new Random();

        return target.OrderBy(x=>(r.Next()));
    }        
}

und Sie können es verwenden, indem Sie die folgenden Schritte ausführen

// use this on any collection that implements IEnumerable!
// List, Array, HashSet, Collection, etc

List<string> myList = new List<string> { "hello", "random", "world", "foo", "bar", "bat", "baz" };

foreach (string s in myList.Randomize())
{
    Console.WriteLine(s);
}

Dies ist meine bevorzugte Methode für ein Mischen, wenn es wünschenswert ist, das Original nicht zu ändern. Es ist eine Variante des Fisher-Yates-Algorithmus "Inside-Out" , der mit jeder aufzählbaren Sequenz funktioniert (die Länge von sourcemuss nicht von Anfang an bekannt sein).

public static IList<T> NextList<T>(this Random r, IEnumerable<T> source)
{
  var list = new List<T>();
  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;
}

Dieser Algorithmus kann auch implementiert werden, indem ein Bereich von 0bis length - 1zugewiesen und die Indizes zufällig erschöpft werden, indem der zufällig ausgewählte Index gegen den letzten Index ausgetauscht wird, bis alle Indizes genau einmal ausgewählt wurden. Dieser obige Code führt genau das Gleiche aus, jedoch ohne die zusätzliche Zuordnung. Welches ist ziemlich ordentlich.

In Bezug auf die RandomKlasse handelt es sich um einen Allzweck-Zahlengenerator (und wenn ich eine Lotterie betreiben würde, würde ich in Betracht ziehen, etwas anderes zu verwenden). Standardmäßig wird auch ein zeitbasierter Startwert verwendet. Eine kleine Lösung des Problems besteht darin, die RandomKlasse mit dem zu setzen, RNGCryptoServiceProvideroder Sie könnten das RNGCryptoServiceProviderin einer ähnlichen Methode (siehe unten) verwenden, um einheitlich ausgewählte zufällige doppelte Gleitkommawerte zu generieren, aber um eine Lotterie durchzuführen, müssen Sie die Zufälligkeit und die Art von verstehen die Zufallsquelle.

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

Der Punkt des Erzeugens eines zufälligen Doppels (ausschließlich zwischen 0 und 1) besteht darin, auf eine ganzzahlige Lösung zu skalieren. Wenn Sie etwas aus einer Liste auswählen müssen, das auf einem zufälligen Double basiert x, ist dies immer 0 <= x && x < 1einfach.

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

Genießen!

Wenn es Ihnen nichts ausmacht, zwei zu verwenden Lists, ist dies wahrscheinlich der einfachste Weg, aber wahrscheinlich nicht der effizienteste oder unvorhersehbarste:

List<int> xList = new List<int>() { 1, 2, 3, 4, 5 };
List<int> deck = new List<int>();

foreach (int xInt in xList)
    deck.Insert(random.Next(0, deck.Count + 1), xInt);

Wenn Sie eine feste Zahl (75) haben, können Sie ein Array mit 75 Elementen erstellen, dann Ihre Liste auflisten und die Elemente an zufällige Positionen im Array verschieben. Sie können die Zuordnung der Listennummer zum Array-Index mithilfe der Fisher-Yates-Zufallswiedergabe generieren .

Ich benutze normalerweise:

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

    List<T> OriginalList = new List<T>();
    List<T> TempList = new List<T>();
    Random random = new Random();
    int length = OriginalList.Count;
    int TempIndex = 0;

    while (length > 0) {
        TempIndex = random.Next(0, length);  // get random value between 0 and original length
        TempList.Add(OriginalList[TempIndex]); // add to temp list
        OriginalList.RemoveAt(TempIndex); // remove from original list
        length = OriginalList.Count;  // get new list <T> length.
    }

    OriginalList = new List<T>();
    OriginalList = TempList; // copy all items from temp list to original list.

Hier ist ein effizienter Shuffler, der ein Byte-Array von Shuffled-Werten zurückgibt. Es mischt nie mehr als nötig. Es kann an der Stelle neu gestartet werden, an der es zuvor aufgehört hat. Meine eigentliche Implementierung (nicht gezeigt) ist eine MEF-Komponente, die einen benutzerdefinierten Ersatzmischer ermöglicht.

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

`

Hier ist eine thread-sichere Möglichkeit, dies zu tun:

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<T> Shuffle<T>(this IEnumerable<T> items)
    {
        return items.OrderBy (i => rng.Next());
    }
}

 public Deck(IEnumerable<Card> initialCards) 
    {
    cards = new List<Card>(initialCards);
    public void Shuffle() 
     }
    {
        List<Card> NewCards = new List<Card>();
        while (cards.Count > 0) 
        {
            int CardToMove = random.Next(cards.Count);
            NewCards.Add(cards[CardToMove]);
            cards.RemoveAt(CardToMove);
        }
        cards = NewCards;
    }

public IEnumerable<string> 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);

}

Eine einfache Änderung der akzeptierten Antwort , die eine neue Liste zurückgibt, anstatt direkt zu arbeiten, und die allgemeinere akzeptiert, IEnumerable<T>wie dies bei vielen anderen Linq-Methoden der Fall ist.

private static Random rng = new Random();

/// <summary>
/// Returns a new list where the elements are randomly shuffled.
/// Based on the Fisher-Yates shuffle, which has O(n) complexity.
/// </summary>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
    var source = list.ToList();
    int n = source.Count;
    var shuffled = new List<T>(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;
}

Ich habe online eine interessante Lösung gefunden.

Mit freundlicher Genehmigung: https://improveandrepeat.com/2018/08/a-simple-way-to-shuffle-your-lists-in-c/

var shuffled = myList.OrderBy (x => Guid.NewGuid ()). ToList ();

Sicher alter Beitrag, aber ich benutze nur eine GUID.

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

Eine GUID ist immer eindeutig, und da sie jedes Mal neu generiert wird, ändert sich das Ergebnis jedes Mal.

Ein sehr einfacher Ansatz für diese Art von Problem besteht darin, eine Reihe von zufälligen Elementtauschvorgängen in der Liste zu verwenden.

Im Pseudocode würde dies so aussehen:

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