Losuj listę <T>

Jaki jest najlepszy sposób na losowe uporządkowanie ogólnej listy w C #? Mam skończony zestaw 75 liczb na liście, do której chciałbym przypisać losową kolejność, aby narysować je dla aplikacji typu loterii.

Przetasuj dowolne (I)Listza pomocą metody rozszerzenia opartej na tasowaniu Fisher-Yates :

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

Stosowanie:

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

Powyższy kod używa bardzo krytykowanej metody System.Random do wybierania kandydatów do zamiany. Jest szybki, ale nie tak losowy, jak powinien. Jeśli potrzebujesz lepszej jakości losowości w tasowaniu, skorzystaj z generatora liczb losowych w System.Security.Cryptography:

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

Proste porównanie jest dostępne na tym blogu (WayBack Machine).

Edycja: Od czasu napisania tej odpowiedzi kilka lat temu wiele osób skomentowało lub napisało do mnie, aby zwrócić uwagę na wielką głupią wadę mojego porównania. Mają oczywiście rację. Nie ma nic złego w System.Random, jeśli jest używany zgodnie z przeznaczeniem. W moim pierwszym przykładzie powyżej utworzyłem zmienną rng w metodzie Shuffle, która prosi o kłopoty, jeśli metoda będzie wywoływana wielokrotnie. Poniżej znajduje się stały, pełny przykład oparty na naprawdę przydatnym komentarzu otrzymanym dziś z @weston tutaj na 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<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;
      }
    }
  }
}

Jeśli musimy tylko tasować przedmioty w całkowicie losowej kolejności (po prostu mieszać przedmioty z listy), wolę ten prosty, ale skuteczny kod, który porządkuje przedmioty według przewodnika ...

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

Jestem trochę zaskoczony wszystkimi niezdarnymi wersjami tego prostego algorytmu tutaj. Fisher-Yates (lub Knuth shuffle) jest nieco trudny, ale bardzo kompaktowy. Dlaczego to jest trudne? Ponieważ musisz zwrócić uwagę na to, czy generator liczb losowych r(a,b)zwraca wartość, gdzie bjest włączająca, czy wyłączna. Zredagowałem również opis Wikipedii, aby ludzie nie śledzili tam pseudokodu i nie tworzyli trudnych do wykrycia błędów. Dla .Net Random.Next(a,b)zwraca liczbę bbez niej, bez zbędnych ceregieli, oto jak można ją zaimplementować w C # /. Net:

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

Wypróbuj ten kod .

Metoda rozszerzenia dla IEnumerable:

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

Pomysłem jest uzyskanie anonimowego obiektu z zamówieniem przedmiotu i losowym, a następnie zmiana kolejności przedmiotów według tego zamówienia i zwrócenie wartości:

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

EDITRemoveAt jest słabość w mojej poprzedniej wersji. To rozwiązanie przezwycięża to.

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

Zwróć uwagę na opcjonalne Random generator, jeśli podstawowa implementacja frameworka Randomnie jest bezpieczna dla wątków lub kryptograficznie wystarczająco silna dla twoich potrzeb, możesz wstrzyknąć swoją implementację do operacji.

W tej odpowiedzi Randommożna znaleźć odpowiednią implementację bezpiecznej dla wątku implementacji kryptograficznie silnej .

Oto pomysł, rozszerz IList w (miejmy nadzieję) skuteczny sposób.

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

Możesz to osiągnąć za pomocą tej prostej metody rozszerzenia

public static class IEnumerableExtensions
{

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

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

i możesz z niego skorzystać, wykonując następujące czynności

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

Jest to moja preferowana metoda odtwarzania losowego, gdy pożądane jest, aby nie modyfikować oryginału. Jest to wariant algorytmu „wywrotu” Fishera – Yatesa, który działa na dowolnej dowolnej sekwencji (długość sourcenie musi być znana od początku).

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

Ten algorytm można również zaimplementować, przydzielając zakres od 0dolength - 1 i losowo wyczerpując indeksy poprzez zamianę na losowo wybrany indeks z ostatniego indeksu aż wszystkie wskaźniki zostały wybrane dokładnie raz. Powyższy kod realizuje dokładnie to samo, ale bez dodatkowego przydziału. Co jest całkiem fajne.

Jeśli chodzi o Randomklasę, jest to generator liczb ogólnego przeznaczenia (a gdybym prowadził loterię, rozważyłbym użycie czegoś innego). Domyślnie opiera się on również na wartości początkowej opartej na czasie. Niewielkim złagodzeniem tego problemu jest zaszczepienie Randomklasy za pomocą RNGCryptoServiceProviderlub można użyć RNGCryptoServiceProvidermetody podobnej do tej (patrz poniżej), aby wygenerować jednolicie wybrane losowe podwójne zmiennoprzecinkowe wartości, ale prowadzenie loterii wymaga zrozumienia losowości i charakteru źródło losowości.

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

Punktem generowania losowego podwójnego (wyłącznie od 0 do 1) jest zastosowanie do skalowania do rozwiązania liczby całkowitej. Jeśli chcesz wybrać coś z listy opartej na losowym podwójnym, xktóry zawsze będzie, 0 <= x && x < 1jest od razu.

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

Cieszyć się!

Jeśli nie masz nic przeciwko użyciu dwóch Lists, jest to prawdopodobnie najłatwiejszy sposób na zrobienie tego, ale prawdopodobnie nie jest to najbardziej wydajny lub nieprzewidywalny:

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

Jeśli masz stałą liczbę (75), możesz utworzyć tablicę z 75 elementami, a następnie wyliczyć listę, przenosząc elementy do losowych pozycji w tablicy. Możesz wygenerować odwzorowanie numeru listy na indeks tablicy za pomocą losowania Fisher-Yates .

Zwykle używam:

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.

Oto wydajny Shuffler, który zwraca tablicę bajtów przetasowanych wartości. Nigdy nie tasuje więcej niż jest to potrzebne. Można go zrestartować od miejsca, w którym poprzednio przerwał. Moja faktyczna implementacja (niepokazana) to komponent MEF, który umożliwia wymianę tasowania określoną przez użytkownika.

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

`

Oto bezpieczny sposób, aby to zrobić:

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

}

Prosta modyfikacja zaakceptowanej odpowiedzi, która zwraca nową listę zamiast pracować w miejscu i akceptuje bardziej ogólne, IEnumerable<T>jak wiele innych metod Linq.

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

Znalazłem interesujące rozwiązanie online.

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

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

Stary post na pewno, ale używam tylko GUID.

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

Identyfikator GUID jest zawsze unikalny i ponieważ jest generowany za każdym razem, gdy wynik zmienia się za każdym razem.

Bardzo prostym podejściem do tego rodzaju problemu jest użycie wielu losowych zamian elementów na liście.

W pseudo-kodzie wyglądałoby to tak:

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