La mejor manera de aleatorizar una matriz con .NET

¿Cuál es la mejor manera de aleatorizar una matriz de cadenas con .NET? Mi matriz contiene aproximadamente 500 cadenas y me gustaría crear una nueva Arraycon las mismas cadenas pero en un orden aleatorio.

Incluya un ejemplo de C # en su respuesta.

Si está en .NET 3.5, puede usar la siguiente frescura IEnumerable (VB.NET, no C #, pero la idea debería ser clara ...):

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();    

Editar: OK y aquí está el código VB.NET correspondiente:

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()

Segunda edición, en respuesta a los comentarios de que System.Random "no es seguro para subprocesos" y "solo es adecuado para aplicaciones de juguete" debido a que devuelve una secuencia basada en el tiempo: como se usa en mi ejemplo, Random () es perfectamente seguro para subprocesos, a menos que está permitiendo que se vuelva a ingresar la rutina en la que aleatoriza la matriz, en cuyo caso necesitará algo así lock (MyRandomArray)para no corromper sus datos, lo que protegerárnd .

Además, debe entenderse bien que System.Random como fuente de entropía no es muy fuerte. Como se señala en la documentación de MSDN , debe usar algo derivado System.Security.Cryptography.RandomNumberGeneratorsi está haciendo algo relacionado con la seguridad. Por ejemplo:

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

La siguiente implementación utiliza el algoritmo de Fisher-Yates, también conocido como Knuth Shuffle. Se ejecuta en tiempo O (n) y se baraja en su lugar, por lo que tiene un mejor rendimiento que la técnica de "ordenar por azar", aunque tiene más líneas de código. Vea aquí algunas medidas comparativas de rendimiento. He usado System.Random, que está bien para fines no criptográficos. *

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

Uso:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* Para matrices más largas, para que el número (extremadamente grande) de permutaciones sea igualmente probable, sería necesario ejecutar un generador de números pseudoaleatorios (PRNG) a través de muchas iteraciones para cada intercambio para producir suficiente entropía. ¡Para una matriz de 500 elementos solo una fracción muy pequeña de los 500 posibles! se podrán obtener permutaciones utilizando un PRNG. Sin embargo, el algoritmo de Fisher-Yates es imparcial y, por lo tanto, la combinación será tan buena como el RNG que use.

Estás buscando un algoritmo de barajado, ¿verdad?

De acuerdo, hay dos formas de hacer esto: los inteligentes, pero la gente, siempre parece que lo malinterpretan y se equivocan, así que tal vez no sea tan inteligente después de todo y la manera tonta como rocas pero a quién le importa porque funciona.

Manera tonta

• Cree un duplicado de su primera matriz, pero etiquete cada cadena con un número aleatorio.
• Ordene la matriz duplicada con respecto al número aleatorio.

Este algoritmo funciona bien, pero asegúrese de que es poco probable que su generador de números aleatorios etiquete dos cadenas con el mismo número. Debido a la llamada paradoja del cumpleaños , esto ocurre con más frecuencia de lo que cabría esperar. Su complejidad temporal es O ( n log n ).

Manera inteligente

Describiré esto como un algoritmo recursivo:

Para barajar una matriz de tamaño n (índices en el rango [0 .. n -1]):

si n = 0

• hacer nada

si n > 0

• (paso recursivo) baraja el primer n -1 elementos de la matriz
• elija un índice aleatorio, x , en el rango [0 .. n -1]
• intercambie el elemento en el índice n -1 con el elemento en el índice x

El equivalente iterativo es caminar un iterador a través de la matriz, intercambiando elementos aleatorios a medida que avanza, pero tenga en cuenta que no puede intercambiar con un elemento después del que señala el iterador. Este es un error muy común y conduce a una mezcla aleatoria sesgada.

La complejidad del tiempo es O ( n ).

Este algoritmo es simple pero no eficiente, O (N ² ). Todos los algoritmos de "ordenar por" suelen ser O (N log N). Probablemente no haga una diferencia por debajo de cientos de miles de elementos, pero lo haría para grandes listas.

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

La razón por la cual es O (N ² ) es sutil: List.RemoveAt () es una operación O (N) a menos que elimine en orden desde el final.

También puede hacer un método de extensión de Matt Howells. Ejemplo.

   namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

Entonces puedes usarlo como:

        string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();

Aleatorizar la matriz es intensivo ya que tienes que desplazarte alrededor de un montón de cadenas. ¿Por qué no simplemente leer al azar de la matriz? En el peor de los casos, incluso podría crear una clase de contenedor con getNextString (). Si realmente necesita crear una matriz aleatoria, entonces podría hacer algo como

for i = 0 -> i= array.length * 5
   swap two strings in random places

El * 5 es arbitrario.

Solo pensando en la parte superior de mi cabeza, podrías hacer esto:

public string[] Randomize(string[] input)
{
  List<string> inputList = input.ToList();
  string[] output = new string[input.Length];
  Random randomizer = new Random();
  int i = 0;

  while (inputList.Count > 0)
  {
    int index = r.Next(inputList.Count);
    output[i++] = inputList[index];
    inputList.RemoveAt(index);
  }

  return (output);
}

Genere una matriz de flotantes aleatorios o entradas de la misma longitud. Ordene esa matriz y realice los intercambios correspondientes en su matriz de destino.

Esto produce un tipo verdaderamente independiente.

Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();

while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}

Jacco, tu solución con un IComparer personalizado no es seguro. Las rutinas de clasificación requieren que el comparador cumpla con varios requisitos para funcionar correctamente. El primero de ellos es la consistencia. Si se llama al comparador en el mismo par de objetos, siempre debe devolver el mismo resultado. (la comparación también debe ser transitiva).

El incumplimiento de estos requisitos puede causar cualquier número de problemas en la rutina de clasificación, incluida la posibilidad de un bucle infinito.

Con respecto a las soluciones que asocian un valor numérico aleatorio con cada entrada y luego las clasifican por ese valor, esto genera un sesgo inherente en la salida porque cada vez que se asignan dos entradas al mismo valor numérico, la aleatoriedad de la salida se verá comprometida. (En una rutina de clasificación "estable", lo que sea primero en la entrada será primero en la salida. Array.Sort no es estable, pero aún existe un sesgo basado en la partición realizada por el algoritmo Quicksort).

Debe pensar un poco sobre el nivel de aleatoriedad que necesita. Si está ejecutando un sitio de póker donde necesita niveles criptográficos de aleatoriedad para protegerse contra un atacante determinado, tiene requisitos muy diferentes a los de alguien que solo quiere aleatorizar una lista de reproducción de canciones.

Para barajar la lista de canciones, no hay problema al usar un PRNG sembrado (como System.Random). Para un sitio de póker, ni siquiera es una opción y debes pensar en el problema mucho más difícil de lo que nadie te hará en stackoverflow. (el uso de un RNG criptográfico es solo el comienzo, debe asegurarse de que su algoritmo no introduzca un sesgo, que tenga suficientes fuentes de entropía y que no exponga ningún estado interno que pueda comprometer la aleatoriedad posterior).

Esta publicación ya ha sido bastante bien respondida: use una implementación de Durstenfeld de la mezcla de Fisher-Yates para obtener un resultado rápido e imparcial. Incluso se han publicado algunas implementaciones, aunque observo que algunas son realmente incorrectas.

Hace un tiempo escribí un par de publicaciones sobre la implementación de shuffles completos y parciales utilizando esta técnica , y (este segundo enlace es donde espero agregar valor) también una publicación de seguimiento sobre cómo verificar si su implementación es imparcial , que se puede usar para verificar cualquier algoritmo aleatorio. Puede ver al final de la segunda publicación el efecto de un simple error en la selección de números aleatorios.

Ok, esto es claramente un golpe de mi parte (se disculpa ...), pero a menudo uso un método bastante general y criptográficamente fuerte.

public static class EnumerableExtensions
{
    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
    {
        var randomIntegerBuffer = new byte[4];
        Func<int> rand = () =>
                             {
                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);
                             };
        return from item in enumerable
               let rec = new {item, rnd = rand()}
               orderby rec.rnd
               select rec.item;
    }
}

Shuffle () es una extensión en cualquier IEnumerable, por lo que puede obtener, por ejemplo, números del 0 al 1000 en orden aleatorio en una lista con

Enumerable.Range(0,1000).Shuffle().ToList()

Este método tampoco dará sorpresas cuando se trata de ordenar, ya que el valor de clasificación se genera y recuerda exactamente una vez por elemento en la secuencia.

No necesitas algoritmos complicados.

Solo una línea simple:

Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

Tenga en cuenta que tenemos que convertir la Arraya una Listprimera, si no se utiliza Listen el primer lugar.

Además, tenga en cuenta que esto no es eficiente para matrices muy grandes. De lo contrario, es limpio y simple.

Esta es una solución de consola de trabajo completa basada en el ejemplo proporcionado aquí :

class Program
{
    static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };

    static void Main()
    {
        var result = Shuffle(words1);
        foreach (var i in result)
        {
            Console.Write(i + " ");
        }
        Console.ReadKey();
    }

   static string[] Shuffle(string[] wordArray) {
        Random random = new Random();
        for (int i = wordArray.Length - 1; i > 0; i--)
        {
            int swapIndex = random.Next(i + 1);
            string temp = wordArray[i];
            wordArray[i] = wordArray[swapIndex];
            wordArray[swapIndex] = temp;
        }
        return wordArray;
    }         
}

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        List<int> numList = new List<int>();
        numList.AddRange(numbers);

        Console.WriteLine("Original Order");
        for (int i = 0; i < numList.Count; i++)
        {
            Console.Write(String.Format("{0} ",numList[i]));
        }

        Random random = new Random();
        Console.WriteLine("\n\nRandom Order");
        for (int i = 0; i < numList.Capacity; i++)
        {
            int randomIndex = random.Next(numList.Count);
            Console.Write(String.Format("{0} ", numList[randomIndex]));
            numList.RemoveAt(randomIndex);
        }
        Console.ReadLine();

Aquí hay una manera simple de usar OLINQ:

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }  
    return sortedList;
}