Aleatorizar uma lista <T>

Qual é a melhor maneira de randomizar a ordem de uma lista genérica em C #? Eu tenho um conjunto finito de 75 números em uma lista à qual gostaria de atribuir uma ordem aleatória, para desenhá-los para um aplicativo do tipo loteria.

Shuffle qualquer (I)Listcom um método de extensão baseado no shuffle de 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;  
    }  
}

Uso:

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

O código acima usa o método System.Random, muito criticado, para selecionar candidatos à troca. É rápido, mas não tão aleatório quanto deveria ser. Se você precisar de uma melhor qualidade de aleatoriedade em seus shuffles, use o gerador de números aleatórios em System.Security.Cryptography da seguinte forma:

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

Uma comparação simples está disponível neste blog (WayBack Machine).

Edit: Desde que escrevi esta resposta há alguns anos, muitas pessoas comentaram ou escreveram para mim, para apontar a grande falha boba da minha comparação. Claro que eles estão certos. Não há nada de errado com o System.Random se ele for usado da maneira que foi planejado. No meu primeiro exemplo acima, instanciamos a variável rng dentro do método Shuffle, que está solicitando problemas se o método for chamado repetidamente. Abaixo está um exemplo fixo e completo, com base em um comentário realmente útil recebido hoje de @weston aqui no 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;
      }
    }
  }
}

Se precisarmos embaralhar itens em uma ordem completamente aleatória (apenas para misturar os itens de uma lista), prefiro esse código simples, porém eficaz, que ordena itens por guia ...

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

Estou um pouco surpreso com todas as versões desajeitadas desse algoritmo simples aqui. Fisher-Yates (ou Knuth shuffle) é um pouco complicado, mas muito compacto. Por que é complicado? Porque você precisa prestar atenção se o gerador de números aleatórios r(a,b)retorna valor onde bé inclusivo ou exclusivo. Também editei a descrição da Wikipedia para que as pessoas não sigam cegamente o pseudocódigo e criem bugs difíceis de detectar. Para .Net, Random.Next(a,b)retorna um número exclusivo b, sem mais delongas, veja como ele pode ser implementado em 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;
}

Experimente este código .

Método de extensão para IEnumerable:

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

A idéia é obter um objeto anônimo com o item e a ordem aleatória e, em seguida, reordenar os itens por esse pedido e retornar o valor:

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

EDIT O RemoveAté uma fraqueza na minha versão anterior. Esta solução supera isso.

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

Observe o opcional Random generator: se a implementação da estrutura base Randomnão for segura para threads ou criptograficamente forte o suficiente para suas necessidades, você poderá injetar sua implementação na operação.

Uma implementação adequada para uma implementação criptograficamente segura de thread-safe Randompode ser encontrada nesta resposta.

Aqui está uma idéia, estenda o IList de uma maneira (esperançosamente) eficiente.

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

Você pode conseguir isso usando este método de extensão simples

public static class IEnumerableExtensions
{

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

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

e você pode usá-lo fazendo o seguinte

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

Esse é o meu método preferido de reprodução aleatória quando é desejável não modificar o original. É uma variante do algoritmo "de dentro para fora" de Fisher – Yates que funciona em qualquer sequência enumerável (o tamanho de sourcenão precisa ser conhecido desde o início).

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

Este algoritmo também pode ser implementado através da atribuição de um intervalo de 0ao length - 1e desgastante aleatoriamente os índices trocando o índice escolhido aleatoriamente com o último índice até que todos os índices foram escolhidos exatamente uma vez. Esse código acima realiza exatamente a mesma coisa, mas sem a alocação adicional. O que é bem legal.

Com relação à Randomclasse, é um gerador de números de uso geral (e, se eu estivesse na loteria, consideraria usar algo diferente). Ele também conta com um valor de semente baseado no tempo por padrão. Um pequeno alívio do problema é propagar a Randomclasse com RNGCryptoServiceProviderou você pode usar o RNGCryptoServiceProvidermétodo semelhante a este (veja abaixo) para gerar valores aleatórios de ponto flutuante duplo aleatoriamente escolhidos de maneira uniforme, mas a execução de uma loteria requer compreensão da aleatoriedade e da natureza de a fonte aleatória.

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

O ponto de gerar um duplo aleatório (entre 0 e 1 exclusivamente) é usar para dimensionar para uma solução inteira. Se você precisar escolher algo de uma lista com base em um duplo aleatório xque sempre será, 0 <= x && x < 1é direto.

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

Aproveitar!

Se você não se importa em usar dois Lists, provavelmente esta é a maneira mais fácil de fazê-lo, mas provavelmente não é a mais eficiente ou imprevisível:

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

Se você tiver um número fixo (75), poderá criar uma matriz com 75 elementos e enumerar sua lista, movendo os elementos para posições aleatórias na matriz. Você pode gerar o mapeamento do número da lista para o índice da matriz usando o shuffle Fisher-Yates .

Eu costumo usar:

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.

Aqui está um Shuffler eficiente que retorna uma matriz de bytes de valores aleatórios. Nunca embaralha mais do que o necessário. Pode ser reiniciado de onde parou anteriormente. Minha implementação real (não mostrada) é um componente MEF que permite a um shuffler de substituição especificado pelo usuário.

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

`

Aqui está uma maneira segura de thread para fazer isso:

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

}

Uma modificação simples da resposta aceita que retorna uma nova lista em vez de trabalhar no local e aceita o mais geral IEnumerable<T>como muitos outros métodos do 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;
}

Eu encontrei uma solução interessante online.

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

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

Post antigo, com certeza, mas eu apenas uso um GUID.

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

Um GUID é sempre único e, uma vez que é regenerado toda vez que o resultado muda a cada vez.

Uma abordagem muito simples para esse tipo de problema é usar várias trocas de elementos aleatórios na lista.

No pseudo-código, seria assim:

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