c# - La mejor forma de aleatorizar una matriz con.NET

algorithm sorting

Question

¿Cuál es la mejor forma 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.

Por favor incluya un ejemplo de C # en su respuesta.

Answer 1

Aleatorio de la matriz es intensivo ya que tiene que cambiar alrededor de un montón de cadenas. ¿Por qué no solo leer al azar de 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 podrías hacer algo como

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

El * 5 es arbitrario.

Answer 2

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

Answer 3

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

De acuerdo, hay dos maneras de hacer esto: el inteligente-pero-la-gente-siempre-parece-malentender-lo-y-conseguir-lo-mal-así-tal-no-es-que-listo-después-todo manera, y la manera de tonto-como-rocas-pero-quién-cuida-porque-funciona.

Forma tonta

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

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

Manera inteligente

Lo describiré 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 los primeros 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 recorrer un iterador a través de la matriz, intercambiando con elementos aleatorios a medida que avance, pero observe que no puede intercambiar con un elemento después del señalado por el iterador. Este es un error muy común y conduce a una confusión parcial.

La complejidad del tiempo es O ( n ).

Answer 4

Esta es una solución completa de la Consola de trabajo 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 5

Esta publicación ya se ha respondido bastante bien: utiliza 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 acerca de la implementación de mezclas completas y parciales usando esta técnica , y (este segundo enlace es donde estoy esperando 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.

Answer 6

Este algoritmo es simple pero no eficiente, O (N ² ). Todos los algoritmos de "ordenar por" son típicamente O (N log N). Probablemente no marque la diferencia debajo de cientos de miles de elementos, pero sería para 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: List.RemoveAt() es una operación O (N) a menos que se elimine en orden desde el final.

Answer 7

Este código mezcla los 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 8

Genera una matriz de flotantes aleatorios o de la misma longitud. Clasifique esa matriz y realice los intercambios correspondientes en su matriz objetivo.

Esto produce un tipo verdaderamente independiente.

Answer 9

Jacco, tu solución es una IComparer personalizada no es segura. Las rutinas Sort 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 cantidad de problemas en la rutina de clasificación, incluida la posibilidad de un ciclo infinito.

En cuanto a las soluciones que asocian un valor numérico aleatorio con cada entrada y luego ordenan por ese valor, estas generan un sesgo inherente en la salida porque cada vez que dos entradas tienen asignado el mismo valor numérico, la aleatoriedad de la salida se verá comprometida. (En una rutina de ordenación "estable", lo primero que esté en la entrada será primero en la salida. Array.Sort no es estable, pero todavía hay un sesgo basado en la partición hecha por el algoritmo Quicksort).

Necesitas pensar un poco sobre qué nivel de aleatoriedad necesitas. Si está ejecutando un sitio de póquer donde necesita niveles criptográficos de aleatoriedad para proteger contra un atacante determinado, tiene requisitos muy diferentes de alguien que solo quiere aleatorizar una lista de reproducción de una canción.

Para mezclar listas de canciones, no hay problema con el uso de un PRNG sin semillas (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 nadie va a hacer por ti en . (El uso de un RNG criptográfico es solo el comienzo; debe asegurarse de que su algoritmo no presente un sesgo, de que tenga suficientes fuentes de entropía y de que no exponga ningún estado interno que pueda comprometer la aleatoriedad posterior).

Answer 10

La siguiente implementación usa el algoritmo de Fisher-Yates . Se ejecuta en O (n) tiempo y se mueve aleatoriamente en su lugar, por lo que tiene un mejor rendimiento que la técnica ''ordenar por azar'', aunque se trata de más líneas de código. Vea here para 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};
new Random().Shuffle(array);

* Para arreglos más largos, para hacer 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, solo una fracción muy pequeña de las 500 posibles! Se podrán obtener permutaciones usando un PRNG. Sin embargo, el algoritmo de Fisher-Yates es imparcial y, por lo tanto, la mezcla será tan buena como el RNG que utilice.

Answer 11

No necesitas algoritmos complicados.

Solo una linea simple:

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

Tenga en cuenta que primero tenemos que convertir la Array en una List , si no utiliza la List en primer lugar.

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

Answer 12

Ok, esto es claramente un bache 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 de cualquier IEnumerable, por lo que puede obtener, digamos, números del 0 al 1000 en orden aleatorio en una lista.

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

Este método tampoco ofrecerá sorpresas a la hora de clasificar, ya que el valor de clasificación se genera y se recuerda exactamente una vez por elemento en la secuencia.

Answer 13

Si usa .NET 3.5, puede usar la siguiente genialidad de IEnumerable (VB.NET, no C #, pero la idea debe quedar 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)

Segunda edición, en respuesta a comentarios de que System.Random "no es seguro para la lectura" y "solo 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 hilos, a menos está permitiendo que la rutina en la que aleatoriza la matriz sea reingresada, en cuyo caso necesitará algo como lock (MyRandomArray) para no corromper sus datos, lo que protegerá a rnd también.

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

Answer 14

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

Answer 15

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 así:

        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 16

        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 17

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