La mejor manera de aleatorizar una matriz con .NET

Question

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

Incluya un ejemplo de C# en su respuesta.

Answer 1

Si está en .NET 3.5, puede usar el siguiente IEnumerable (VB.NET, no C#, pero la idea debe 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 juguetes" 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 permita que se vuelva a ingresar la rutina en la que aleatoriza la matriz, en cuyo caso necesitará algo como lock (MyRandomArray) de todos modos para no corromper sus datos, lo que protegerá rnd también.

Además, debe entenderse bien que System.Random como fuente de entropía no es muy potente.Como se señala en el documentación de MSDN, deberías usar algo derivado de System.Security.Cryptography.RandomNumberGenerator si estás 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]);
    }

Answer 2

La siguiente implementación utiliza el Algoritmo de Fisher-Yates También conocido como Knuth Shuffle.Se ejecuta en tiempo O(n) y se mezcla en el lugar, por lo que tiene un mejor rendimiento que la técnica de "ordenar aleatoriamente", aunque tiene más líneas de código.Ver aquí para algunas mediciones comparativas de desempeño.He utilizado 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 que cada intercambio produzca suficiente entropía.¡Para una matriz de 500 elementos sólo una fracción muy pequeña de los 500 posibles!Las permutaciones serán posibles de obtener usando un PRNG.Sin embargo, el algoritmo de Fisher-Yates es imparcial y, por lo tanto, la reproducción aleatoria será tan buena como el RNG que utilice.

Answer 3

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

Bien, hay dos formas de hacer esto:los inteligentes, pero-la-gente-siempre-parece-malinterpretarlo-y-equivocarse-así que-tal vez-no-sea-tan-inteligente-después de todo, y los tontos-como-piedras- 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.
• Ordena 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 sucede con más frecuencia de lo que cabría esperar.Su complejidad temporal es O(norte registro norte).

manera inteligente

Describiré esto como un algoritmo recursivo:

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

si norte = 0

• hacer nada

si norte > 0

• (paso recursivo) barajar el primero norte-1 elementos de la matriz
• elegir un índice aleatorio, X, en el rango [0..norte-1]
• intercambiar el elemento en el índice norte-1 con el elemento en el índice X

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

La complejidad del tiempo es O(norte).

Answer 4

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 debajo de cientos de miles de elementos, pero sí lo haría en listas grandes.

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 que es O(N)²) es sutil: Lista.RemoveAt() es una operación O(N) a menos que la elimine en orden desde el final.

Answer 5

También puedes crear un método de extensión con 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>();

Answer 6

Aleatorizar la matriz es intensivo ya que hay que desplazar un montón de cadenas.¿Por qué no simplemente leer aleatoriamente desde la matriz?En el peor de los casos, incluso podría crear una clase contenedora con getNextString().Si realmente necesitas crear una matriz aleatoria, entonces puedes hacer algo como

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

El *5 es arbitrario.

Answer 7

Pensando en lo que se me viene a la 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);
}

Answer 8

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

Esto produce un tipo verdaderamente independiente.

Answer 9

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

Answer 10

Jacco, tu solución es un IComparer personalizado que 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 coherencia.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 numerosos 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 ordenan según ese valor, generan un sesgo inherente en la salida porque cada vez que a dos entradas se les asigna el mismo valor numérico, la aleatoriedad de la salida se verá comprometida.(En una rutina de clasificación "estable", lo que esté primero en la entrada será el 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 qué nivel de aleatoriedad necesita.Si está ejecutando un sitio de póquer 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 en usar un PRNG predefinido (como System.Random).Para un sitio de póquer, ni siquiera es una opción y debes pensar en el problema mucho más de lo que cualquiera lo haría por ti en stackoverflow.(Usar 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 comprometa la aleatoriedad posterior).

Answer 11

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

Escribí un par de publicaciones hace un tiempo sobre implementar mezclas totales y parciales usando 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 utilizar para comprobar cualquier algoritmo de reproducción aleatoria.Puedes ver al final del segundo post el efecto que puede tener un simple error en la selección de números aleatorios.

Answer 12

Ok, esto es claramente un obstáculo por mi parte (se disculpa...), pero a menudo uso un método bastante general y criptográficamente sólido.

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 de cualquier IEnumerable, por lo que se puede obtener, digamos, 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 de la secuencia.

Answer 13

No necesitas algoritmos complicados.

Sólo una simple línea:

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

Tenga en cuenta que necesitamos convertir el Array a un List primero, si no usas List en primer lugar.

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

Answer 14

Esta es una solución de consola completa y funcional 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;
    }         
}

Answer 15

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

Answer 16

Este código mezcla números en una matriz.

using System;

// ...
    static void Main(string[] args)
    {
        Console.ForegroundColor = ConsoleColor.Cyan;
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Shuffle(numbers);

        for (int i = 0; i < numbers.Length; i++)
            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
        Console.WriteLine();

        string[] words = { "this", "is", "a", "string", "of", "words" };
        Shuffle(words);

        for (int i = 0; i < words.Length; i++)
            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
        Console.WriteLine();

        Console.ForegroundColor = ConsoleColor.Gray;
        Console.Write("Press any key to quit . . . ");
        Console.ReadKey(true);
    }

    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();

        for (int i = 0; i < array.Length; i++)
        {
            T temporary = array[i];
            int intrandom = random.Next(array.Length);
            array[i] = array[intrandom];
            array[intrandom] = temporary;
        }
    }

Answer 17

A continuación se muestra una forma sencilla de utilizar 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);

Answer 18

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