Losowanie listy

Jeśli musimy tylko przetasować elementy w całkowicie przypadkowej kolejności( po prostu mieszać elementy na liście), wolę ten prosty, ale skuteczny kod, który zamawia elementy za pomocą guid...

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

Jestem trochę zaskoczony wszystkimi niezgrabnymi wersjami tego prostego algorytmu. Fisher-Yates (lub Knuth shuffle) jest nieco skomplikowany, ale bardzo zwarty. Jeśli przejdziesz do Wikipedii, zobaczysz wersję tego algorytmu, która ma pętlę for w odwrotnej kolejności i wiele osób nie zdaje się rozumieć, dlaczego jest ona odwrotna. Kluczowym powodem jest to, że ta wersja algorytmu zakłada, że generator liczb losowych Random(n) do twojej dyspozycji ma dwie następujące właściwości:

1. przyjmuje n jako pojedyncze parametr wejściowy.
2. Zwraca liczbę od 0 do n włącznie .

Jednak. Net generator liczb losowych nie spełnia właściwości # 2. Random.Next(n) zamiast tego Zwraca liczbę od 0 do N-1 włącznie. Jeśli spróbujesz użyć for-loop w odwrotnej kolejności, będziesz musiał wywołać Random.Next(n+1), co dodaje jedną dodatkową operację.

Jednak. NET generator liczb losowych ma inną ładną funkcję Random.Next(a,b), która zwraca a do B-1 włącznie. To rzeczywiście idealnie pasuje do implementacja tego algorytmu, który ma normalną pętlę for. Więc bez zbędnych ceregieli, oto prawidłowa, wydajna i kompaktowa implementacja:

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

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

Metoda rozszerzenia dla liczby mnogiej:

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

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

EDIT RemoveAt jest słabością 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 Random nie jest wystarczająco bezpieczna dla wątków lub kryptograficznie silna dla Twoich potrzeb, możesz wprowadzić swoją implementację do operacji.

Odpowiednia implementacja dla bezpiecznej dla wątku kryptograficznie silnej implementacji Random znajduje się w tej odpowiedzi.

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ąć używając 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 go użyć, 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);
}

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

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

Jest to moja preferowana metoda shuffle, gdy pożądane jest, aby nie modyfikować oryginału. Jest to wariant algorytmu Fishera–Yatesa "inside-out" , który działa na dowolnym ciągu liczbowym(długość source nie 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;
}

Algorytm ten może być również zaimplementowany przez przydzielenie zakresu od 0 do length - 1 i losowo wyczerpanie indeksów poprzez zamianę losowo wybranego indeksu z ostatnim indeksem, dopóki wszystkie indeksy nie zostaną wybrane dokładnie raz. Powyższy kod osiąga dokładnie to samo, ale bez dodatkowego przydziału. Co jest całkiem niezłe.

W odniesieniu do klasy Random jest to generator liczb ogólnego przeznaczenia (i gdybym prowadził loterię, rozważyłbym użycie czegoś innego). Domyślnie opiera się również na wartości zalążkowej opartej na czasie. Małym złagodzeniem problemu jest zalanie klasy Random za pomocą RNGCryptoServiceProvider lub użycie RNGCryptoServiceProvider w metodzie podobnej do tej (patrz poniżej) do wygenerowania jednolicie wybrane losowe podwójne wartości zmiennoprzecinkowe, ale prowadzenie loterii wymaga zrozumienia losowości i natury źródła losowości.

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

Punkt generowania losowego dubletu (między 0 a 1) jest używany do skalowania do rozwiązania liczby całkowitej. Jeśli musisz wybrać coś z listy na podstawie losowego podwójnego x, to zawsze będzie 0 <= x && x < 1, to prosto do przodu.

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

Jeśli nie masz nic przeciwko użyciu dwóch Lists, to prawdopodobnie jest to najprostszy sposób, ale prawdopodobnie nie najbardziej skuteczny 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);

Oto wydajny Tasownik, który zwraca tablicę bajtów tasowanych wartości. Nigdy nie tasuje więcej niż jest to potrzebne. Można go ponownie uruchomić od miejsca, w którym wcześniej został przerwany. Moja rzeczywista implementacja (nie pokazana) jest komponentem MEF, który umożliwia użytkownikowi określony zamiennik shuffler.

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

}

Idea to get anonimous object with item and random order and then reorder items by this order and return value:

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

Oto wątek-bezpieczny sposób na to:

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

Prosta modyfikacja zaakceptowanej odpowiedzi , która zwraca nową listę zamiast działać na 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;
}

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

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

GUID jest zawsze unikalny, a ponieważ jest regenerowany za każdym razem, wynik zmienia się za każdym razem.

Bardzo prostym podejściem do tego rodzaju problemu jest użycie liczby losowych wymian 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