Pregunta Aleatorizar una lista


¿Cuál es la mejor manera de aleatorizar el orden de una lista genérica en C #? Tengo un conjunto finito de 75 números en una lista a la que me gustaría asignar un orden aleatorio, para poder dibujarlos para una aplicación tipo lotería.


652
2017-11-07 19:28


origen


Respuestas:


Baraja cualquier (I)List con un método de extensión basado en Fisher-Yates baraja:

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

El código anterior usa el muy criticado método System.Random para seleccionar candidatos de intercambio. Es rápido pero no tan aleatorio como debería ser. Si necesita una mejor calidad de aleatoriedad en sus mezclas, use el generador de números aleatorios en System.Security.Cryptography como esta:

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

Una comparación simple está disponible en este blog (Máquina WayBack).

Editar: Desde que escribí esta respuesta hace un par de años, muchas personas me han comentado o escrito para señalar el gran error en mi comparación. Por supuesto, tienen razón. No hay nada de malo con System.Random si se usa de la manera en que fue diseñado. En mi primer ejemplo anterior, ejemplifico la variable rng dentro del método Shuffle, que está buscando problemas si el método se va a llamar repetidamente. A continuación se muestra un ejemplo completo y fijo basado en un comentario realmente útil recibido hoy de @weston aquí en 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;
      }
    }
  }
}

922
2017-08-11 20:07



Si solo tenemos que mezclar los elementos en un orden completamente aleatorio (solo para mezclar los elementos en una lista), prefiero este código simple pero eficaz que ordena artículos por guía ...

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

250
2017-11-23 23:34



Estoy un poco sorprendido por todas las versiones torpes de este algoritmo simple aquí. Fisher-Yates (o Knuth shuffle) es un poco complicado pero muy compacto. Si vas a Wikipedia, verás una versión de este algoritmo que tiene for-loop en reversa y mucha gente realmente no parece entender por qué está en reversa. La razón clave es que esta versión de algoritmo supone que el generador de números aleatorios Random(n) a su disposición tiene las siguientes dos propiedades:

  1. Acepta n como parámetro de entrada único.
  2. Devuelve el número de 0 a n inclusivo.

Sin embargo, el generador de números aleatorios .Net no cumple con la propiedad # 2. los Random.Next(n) en su lugar devuelve el número de 0 a n-1 inclusive. Si intentas utilizar for-loop en reversa, deberás llamar Random.Next(n+1) que agrega una operación adicional.

Sin embargo, el generador de números aleatorios .Net tiene otra función agradable Random.Next(a,b) que devuelve a a b-1 inclusive. Esto realmente encaja perfectamente con la implementación de este algoritmo que tiene for-loop normal. Entonces, sin más preámbulos, aquí está la implementación correcta, eficiente y compacta:

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

85
2018-03-26 17:41



Método de extensión para IEnumerable:

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

64
2017-08-11 08:54



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

10
2017-11-07 21:18



EDITAR los RemoveAt es una debilidad en mi versión anterior. Esta solución supera eso.

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

Tenga en cuenta el opcional Random generator, si la implementación del marco base de Random no es seguro para subprocesos o criptográficamente lo suficientemente fuerte para sus necesidades, puede inyectar su implementación en la operación.

Una implementación adecuada para un hilo seguro criptográficamente fuerte Randomimplementación se puede encontrar en esta respuesta.


Aquí hay una idea, amplíe IList de una manera (con suerte) 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]];
}


8
2017-10-27 08:43



Puedes lograr eso usando este método de extensión simple

public static class IEnumerableExtensions
{

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

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

y puedes usarlo haciendo lo siguiente

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

6
2017-08-24 17:48



Usualmente uso:

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

4
2017-11-07 19:35



Si tiene un número fijo (75), puede crear una matriz con 75 elementos, luego enumerar su lista y mover los elementos a posiciones aleatorias en la matriz. Puede generar la asignación del número de lista al índice de matriz usando el Fisher-Yates baraja.


3
2017-11-07 19:35