Aleatorizar una lista <T>

855

¿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 de tipo lotería.

mirezus
fuente
3
Hay un problema abierto para integrar esta funcionalidad a .NET: github.com/dotnet/corefx/issues/461
Natan
55
Puede que le interese este paquete NuGet , que contiene métodos de extensión para mezclar IList <T> e IEnumerable <T> utilizando el algoritmo de Fisher-Yates mencionado a continuación
ChaseMedallion
3
@Natan cerraron el problema porque alguien "trabajó en muchos proyectos y desarrolló muchas bibliotecas y nunca tuvo la necesidad de tal método" que me molestó. Ahora tenemos que investigarnos a nosotros mismos, buscar las mejores implementaciones, perder el tiempo para simplemente reinventar la rueda.
Vitalii Isaenko
1
¿Estoy viendo esto bien? ¿Ni una sola respuesta funcional válida después de 10 años? Tal vez necesitamos otra recompensa por una solución que aborde la cantidad de entropía necesaria, para barajar una lista con 75 números $ log2 (75!) = 364 $ y cómo podemos obtener esto. Sería necesario volver a sembrar incluso un RNG criptográficamente seguro con 256 bits de entropía al menos una vez durante un shuffle de fisher-yates.
Falco
1
Y si el programador habitual no puede resolver este problema, ¿hemos estado jugando el mismo 0.01% de los posibles juegos de solitario para siempre?
Falco

Respuestas:

1137

Mezcle cualquiera (I)Listcon un método de extensión basado en la mezcla aleatoria 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();

El código anterior utiliza el método System.Random muy criticado 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 barajas, use el generador de números aleatorios en System.Security.Cryptography de esta manera:

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 (WayBack Machine).

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 tonto en mi comparación. Por supuesto que tienen razón. No hay nada de malo en System.Random si se usa de la forma prevista. En mi primer ejemplo anterior, ejemplifico la variable rng dentro del método Shuffle, que está pidiendo problemas si el método se 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;
      }
    }
  }
}
granada
fuente
32
¿Qué pasa si list.Count es> Byte.MaxValue? Si n = 1000, entonces 255/1000 = 0, entonces el ciclo do será un ciclo infinito ya que el cuadro [0] <0 siempre es falso.
AndrewS
18
Me gustaría señalar que la comparación es errónea. El uso de <code> new Random () </code> en un bucle es el problema, no la aleatoriedad de <code> Random </code> Explicación
Sven
99
Es una buena idea pasar una instancia de Aleatorio al método Reproducción aleatoria en lugar de crearla en el interior como si estuviera llamando a Reproducción aleatoria muchas veces seguidas (por ejemplo, barajando muchas listas cortas), todas las listas se barajarán en el mismo manera (por ejemplo, el primer elemento siempre se mueve a la posición 3).
Mark Heath
77
Solo hacer Random rng = new Random();un staticresolvería el problema en la publicación de comparación. Como cada llamada subsiguiente seguiría de las llamadas anteriores, el último resultado aleatorio.
Weston
55
# 2, no está claro que la versión con el generador Crypto funcione porque el rango máximo de un byte es 255, por lo que cualquier lista más grande que esa no se barajará correctamente.
Mark Sowul
336

Si solo necesitamos mezclar elementos en un orden completamente aleatorio (solo para mezclar los elementos en una lista), prefiero este código simple pero efectivo que ordena elementos por guid ...

var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();
usuario453230
fuente
40
Los GUID están destinados a ser únicos, no aleatorios. Una parte está basada en la máquina y otra parte está basada en el tiempo y solo una pequeña parte es aleatoria. blogs.msdn.com/b/oldnewthing/archive/2008/06/27/8659071.aspx
Despertar
99
Esta es una buena solución elegante. Si desea algo más que un guid para generar aleatoriedad, simplemente ordene por otra cosa. Por ejemplo: var shuffledcards = cards.OrderBy(a => rng.Next()); compilr.com/grenade/sandbox/Program.cs
granada
20
Por favor no. Esto está mal. "ordenar al azar" NO es una confusión: introduces un sesgo y, lo que es peor, te arriesgas a ir en bucles infinitos
Vito De Tullio
78
@VitoDeTullio: Estás recordando mal. Corre el riesgo de bucles infinitos cuando proporciona una función de comparación aleatoria ; Se requiere una función de comparación para producir un orden total consistente . Una clave aleatoria está bien. Esta sugerencia es incorrecta porque no se garantiza que las guías sean aleatorias , no porque la técnica de ordenar por una clave aleatoria sea incorrecta.
Eric Lippert
24
@Doug: NewGuidsolo garantiza que te da un GUID único. No garantiza la aleatoriedad. Si está utilizando un GUID para un propósito que no sea crear un valor único , lo está haciendo mal.
Eric Lippert
120

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. ¿Por qué es complicado? Porque debe prestar atención a si su generador de números aleatorios r(a,b)devuelve valor donde bes inclusivo o exclusivo. También he editado la descripción de Wikipedia para que la gente no siga ciegamente el pseudocódigo allí y cree errores difíciles de detectar. Para .Net, Random.Next(a,b)devuelve un número exclusivo, bsin más preámbulos, así es como se puede implementar en 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;
}

Prueba este código .

Shital Shah
fuente
¿No sería mejor cambiar rnd (i, list.Count) a rnd (0, list.Count) para poder intercambiar cualquier tarjeta?
Donuts
16
@Donuts - no. Si haces eso, agregarás sesgo en barajado.
Shital Shah
2
Al separar Swap <T> en un método separado, parece que causa muchas asignaciones T innecesarias para temp.
Clay
2
Yo diría que LINQ podría potencialmente ralentizar el rendimiento de la mezcla, y esa sería una razón para no usarlo, especialmente dada la relativa simplicidad del código.
winglerw28
77
Cuándo i = list.Count - 1, es decir, la última iteración, rnd.Next(i, list.Count)te devolverá i. Por lo tanto, necesita i < list.Count -1como condición de bucle. Bueno, no lo 'necesita', pero ahorra 1 iteración;)
Pod
78

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());
}
Denis
fuente
3
Tenga en cuenta que esto no es seguro para subprocesos, incluso si se usa en una lista segura para subprocesos
BlueRaja - Danny Pflughoeft
1
¿Cómo le damos la lista <cadena> a esta función?
MonsterMMORPG
8
Existen dos problemas importantes con este algoritmo: - OrderByutiliza una variante QuickSort para ordenar los elementos por sus teclas (aparentemente aleatorias). El rendimiento de QuickSort es O (N log N) ; en contraste, un shuffle de Fisher-Yates es O (N) . Para una colección de 75 elementos, esto puede no ser un gran problema, pero la diferencia será pronunciada para colecciones más grandes.
John Beyer
10
... - Random.Next()puede producir una distribución de valores razonablemente pseudoaleatoria, pero no garantiza que los valores sean únicos. La probabilidad de duplicar claves crece (no linealmente) con N hasta que alcanza la certeza cuando N alcanza 2 ^ 32 + 1. El OrderByQuickSort es un tipo estable ; por lo tanto, si a varios elementos se les asigna el mismo valor de índice pseudoaleatorio, entonces su orden en la secuencia de salida será el mismo que en la secuencia de entrada; por lo tanto, se introduce un sesgo en el "shuffle".
John Beyer
27
@JohnBeyer: Hay problemas mucho, mucho mayores que esa fuente de sesgo. Solo hay cuatro mil millones de semillas posibles para Aleatorio, que es mucho, mucho menos que el número de posibles mezclas de un conjunto de tamaño moderado. Solo se puede generar una pequeña fracción de los posibles barajamientos. Ese sesgo eclipsa el sesgo debido a colisiones accidentales.
Eric Lippert
16

La idea es obtener un objeto anónimo con un artículo y un orden aleatorio y luego reordenar los artículos por este orden y valor de retorno:

var result = items.Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList()
Andrey Kucher
fuente
3
mejor solución one liner
vipin8169
1
Que se está perdiendo un punto y coma en el extremo FYI
reggaeguitar
Si alguien no está seguro acerca de rnd agregue esto antes del código anterior Random rnd = new Random ();
Greg Trevellick
10
    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;
    }
Adam Tegen
fuente
44
¿No deberías hacer algo como var listCopy = list.ToList()evitar que todos los elementos salgan de la lista entrante? Realmente no entiendo por qué querrías mutar esas listas para vaciarlas.
Chris Marisic
9

EDITAR El RemoveAtes 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 lo opcional Random generator, si la implementación del marco base de Randomno es segura para subprocesos o criptográficamente lo suficientemente fuerte para sus necesidades, puede inyectar su implementación en la operación.

En Randomesta respuesta se puede encontrar una implementación adecuada para una implementación criptográfica segura para subprocesos .


He aquí una idea, extienda 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]];
}

Jodrell
fuente
Ver stackoverflow.com/questions/4412405/… . ya debes estar al tanto.
nawfal
@nawfal ve mi implementación mejorada.
Jodrell
1
hmm lo suficientemente justo. Es GetNexto Next?
nawfal
4

Puede lograrlo utilizando este sencillo método de extensión

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);
}
Shehab Fawzy
fuente
3
Mantendría la Randominstancia de clase fuera de la función como una staticvariable. De lo contrario, puede obtener la misma semilla de aleatorización del temporizador si se llama en una sucesión rápida.
Lemonseed
Una nota interesante: si crea una instancia de la clase Aleatoria rápidamente dentro de un ciclo, digamos entre 0 ms y 200 ms entre sí, entonces tiene una probabilidad muy alta de obtener la misma semilla de aleatorización, lo que resulta en resultados repetidos. Sin embargo, puede evitar esto mediante Random rand = new Random (Guid.NewGuid (). GetHashCode ()); Esto efectivamente obliga a la aleatorización a derivarse del Guid.NewGuid ()
Baaleos
4

Este es mi método preferido de barajar cuando es deseable no modificar el original. Es una variante del algoritmo "de adentro hacia afuera" de Fisher-Yates que funciona en cualquier secuencia enumerable ( sourceno es necesario conocer la longitud desde el principio).

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 también se puede implementar mediante la asignación de un rango de 0a length - 1y agotando al azar los índices mediante el canje el índice elegido al azar con el último índice hasta que todos los índices se han elegido exactamente una vez. Este código anterior logra exactamente lo mismo pero sin la asignación adicional. Lo cual es bastante bueno.

Con respecto a la Randomclase, es un generador de números de propósito general (y si estuviera ejecutando una lotería, consideraría usar algo diferente). También se basa en un valor inicial basado en el tiempo de forma predeterminada. Un pequeño alivio del problema es sembrar la Randomclase con el RNGCryptoServiceProvidero podría usarlo RNGCryptoServiceProvideren un método similar a este (vea a continuación) para generar valores aleatorios de punto flotante doble elegidos uniformemente, pero ejecutar una lotería requiere bastante comprensión de la aleatoriedad y la naturaleza de La fuente de aleatoriedad.

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

El punto de generar un doble aleatorio (entre 0 y 1 exclusivamente) es usar para escalar a una solución entera. Si necesita elegir algo de una lista basada en un doble aleatorio xque siempre será 0 <= x && x < 1sencillo.

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

¡Disfrutar!

John Leidegren
fuente
4

Si no le importa usar dos Lists, entonces esta es probablemente la forma más fácil de hacerlo, pero probablemente no sea la más eficiente o impredecible:

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);
Xelights
fuente
3

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

dmo
fuente
3

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);
}
alberteína
fuente
list.RemoveAt es una operación O (n), que hace que esta implementación sea prohibitivamente lenta.
George Polevoy
1
    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.
usuario7767814
fuente
0

Aquí hay un barajador eficiente que devuelve una matriz de bytes de valores barajados. Nunca baraja más de lo necesario. Se puede reiniciar desde donde lo dejó anteriormente. Mi implementación real (no se muestra) es un componente MEF que permite un barajador de reemplazo especificado por el usuario.

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

``

BSalita
fuente
0

Aquí hay una forma segura de subprocesos para hacer esto:

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());
    }
}
Christopher Stevenson
fuente
0
 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);

}
sumit laddha
fuente
2
¡Bienvenido a Stack Overflow! Considere agregar alguna explicación a su respuesta, en lugar de solo un gran bloque de código. Nuestro objetivo aquí es educar a las personas para que comprendan la respuesta y puedan aplicarla en otras situaciones. Si comenta su código y agrega una explicación, hará que su respuesta sea más útil no solo para la persona que hizo la pregunta esta vez, sino para cualquier persona en el futuro que pueda tener el mismo problema.
starsplusplus
44
La mayor parte de este código es completamente irrelevante para la pregunta, y la única parte útil básicamente repite la respuesta de Adam Tegen de hace casi 6 años.
TC
0

Una modificación simple de la respuesta aceptada que devuelve una nueva lista en lugar de funcionar en el lugar, y acepta el más general IEnumerable<T>como lo hacen muchos otros métodos de 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;
}
Extragorey
fuente
-5

Publicación antigua con seguridad, pero solo uso un GUID.

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

Un GUID siempre es único, y dado que se regenera cada vez que el resultado cambia cada vez.

DavidMc
fuente
Compacto, pero ¿tiene alguna referencia sobre la clasificación de nuevosGuids consecutivos para que sean aleatorios de alta calidad? Algunas versiones de quid / uuid tienen marcas de tiempo y otras partes no aleatorias.
Johan Lundberg
8
Esta respuesta ya se ha dado, y peor aún, está diseñada para la unicidad, no para la aleatoriedad.
Alex Angas
-7

Un enfoque muy simple para este tipo de problema es usar un número de intercambio de elementos aleatorios en la lista.

En pseudocódigo esto se vería así:

do 
    r1 = randomPositionInList()
    r2 = randomPositionInList()
    swap elements at index r1 and index r2 
for a certain number of times
Aleris
fuente
1
Un problema con este enfoque es saber cuándo parar. También tiene una tendencia a exagerar cualquier sesgo en el generador de números pseudoaleatorios.
Mark Bessey, el
3
Si. Altamente ineficiente. No hay ninguna razón para usar un enfoque como este cuando existen enfoques mejores y más rápidos que son igual de simples.
PeterAllenWebb
1
no muy eficiente o efectivo ... Ejecutarlo N veces probablemente dejaría muchos elementos en su posición original.
NSjonas