Melhor maneira de randomizar uma matriz com o .NET

Qual é a melhor maneira de randomizar uma matriz de strings com o .NET? Meu array contém cerca de 500 strings e eu gostaria de criar um novo Array com as mesmas strings, mas em ordem aleatória.

Por favor inclua um exemplo C # na sua resposta.

Se você está no .NET 3.5, você pode usar o seguinte coolness IEnumerable (VB.NET, não C #, mas a idéia deve ser clara …):

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

Edit: OK e aqui está o código VB.NET correspondente:

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

Segunda edição, em resposta aos comentários de que System.Random “não é threadsafe” e “apenas adequado para aplicativos de brinquedo” devido ao retorno de uma sequência baseada em tempo: como usado no meu exemplo, Random () é perfeitamente thread-safe, a menos você está permitindo que a rotina em que você aleatoriamente a matriz seja reinserida, e nesse caso você precisará de algo como lock (MyRandomArray) para não corromper seus dados, o que também protegerá o rnd .

Além disso, deve ser bem entendido que o System.Random como fonte de entropia não é muito forte. Conforme observado na documentação do MSDN , você deve usar algo derivado de System.Security.Cryptography.RandomNumberGenerator se estiver fazendo algo relacionado à segurança. Por exemplo:

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

A implementação a seguir usa o algoritmo de Fisher-Yates . Ele é executado em O (n) time e shuffles no lugar, então é melhor do que a técnica ‘sort by random’, embora seja mais linhas de código. Veja aqui algumas medições de desempenho comparativas. Eu usei System.Random, o que é bom para propósitos não criptocharts. *

 static class RandomExtensions { public static void Shuffle (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 matrizes mais longas, a fim de tornar o número (extremamente grande) de permutações igualmente provável, seria necessário executar um gerador de números pseudo-randoms (PRNG) através de várias iterações para cada troca para produzir entropia suficiente. Para uma matriz de 500 elementos, apenas uma pequena fração dos 500 possíveis! permutações será possível obter usando um PRNG. No entanto, o algoritmo de Fisher-Yates é imparcial e, portanto, o shuffle será tão bom quanto o RNG que você usa.

Você está procurando por um algoritmo de embaralhamento, certo?

Ok, existem duas maneiras de fazer isso: a inteligente-mas-as-pessoas-sempre-parecem-não-entender-e-erradas-então-talvez-não-que-inteligente-depois de tudo caminho, e o jeito burro-como-rochas-mas-quem-cuida-porque-trabalha.

Caminho mudo

  • Crie uma duplicata do seu primeiro array, mas marque cada string com um número random.
  • Classifique a matriz duplicada em relação ao número random.

Esse algoritmo funciona bem, mas é improvável que seu gerador de números randoms marque duas strings com o mesmo número. Por causa do chamado Paradoxo de Aniversário , isso acontece com mais frequência do que você poderia esperar. Sua complexidade de tempo é O ( n log n ).

Maneira inteligente

Vou descrever isso como um algoritmo recursivo:

Para misturar uma matriz de tamanho n (índices no intervalo [0 .. n -1]):

se n = 0

  • fazer nada

se n > 0

  • (etapa recursiva) embaralhe os primeiros n -1 elementos da matriz
  • escolha um índice random, x , no intervalo [0 .. n -1]
  • trocar o elemento no índice n -1 com o elemento no índice x

O equivalente iterativo é percorrer um iterador pelo array, trocando elementos randoms à medida que você avança, mas observe que não é possível alternar com um elemento após o que o iterador aponta. Este é um erro muito comum e leva a um shuffle tendencioso.

A complexidade do tempo é O ( n ).

Esse algoritmo é simples, mas não eficiente, O (N 2 ). Todos os algoritmos “order by” são tipicamente O (N log N). Provavelmente não faz diferença abaixo de centenas de milhares de elementos, mas para grandes listas.

 var stringlist = ... // add your values to stringlist var r = new Random(); var res = new List(stringlist.Count); while (stringlist.Count >0) { var i = r.Next(stringlist.Count); res.Add(stringlist[i]); stringlist.RemoveAt(i); } 

A razão pela qual é O (N 2 ) é sutil: List.RemoveAt () é uma operação O (N), a menos que você remova em ordem do final.

Você também pode fazer um método de extention de Matt Howells. Exemplo.

  namespace System { public static class MSSystemExtenstions { private static Random rng = new Random(); public static void Shuffle(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; } } } } 

Então você pode apenas usá-lo 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(); 

A randomização do array é intensiva, já que você precisa mudar um monte de strings. Por que não apenas ler aleatoriamente da matriz? No pior dos casos, você poderia até mesmo criar uma class wrapper com um getNextString (). Se você realmente precisa criar um array random, então você poderia fazer algo como

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

O * 5 é arbitrário.

Apenas pensando no topo da minha cabeça, você poderia fazer isso:

 public string[] Randomize(string[] input) { List 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); } 

Este post já foi muito bem respondido – use uma implementação Durstenfeld do shuffle da Fisher-Yates para um resultado rápido e imparcial. Houve até algumas implementações postadas, embora eu note que algumas estão incorretas.

Eu escrevi algumas postagens um tempo atrás sobre a implementação de shuffles completos e parciais usando essa técnica , e (este segundo link é onde eu espero adicionar valor) também um post de acompanhamento sobre como verificar se sua implementação é imparcial , que pode ser usado para verificar qualquer algoritmo random. Você pode ver no final do segundo post o efeito de um simples erro no número random que a seleção pode fazer.

Gere um array de floats randoms ou ints do mesmo tamanho. Classifique essa matriz e faça as trocas correspondentes na sua matriz de destino.

Isso produz um tipo verdadeiramente independente.

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

Jacco, sua solução é um IComparer personalizado não é seguro. As rotinas de sorting exigem que o comparador esteja em conformidade com vários requisitos para funcionar corretamente. O primeiro deles é a consistência. Se o comparador for chamado no mesmo par de objects, sempre deverá retornar o mesmo resultado. (a comparação também deve ser transitiva).

O não cumprimento desses requisitos pode causar vários problemas na rotina de sorting, incluindo a possibilidade de um loop infinito.

Em relação às soluções que associam um valor numérico random a cada input e, em seguida, classificam por esse valor, elas são direcionadas a um viés inerente na saída, pois a qualquer momento duas inputs recebem o mesmo valor numérico, a aleatoriedade da saída será comprometida. (Em uma rotina de ordenação “estável”, o que ocorrer primeiro na input será o primeiro na saída. O Array.Sort não é estável, mas ainda existe um viés baseado no particionamento feito pelo algoritmo Quicksort).

Você precisa pensar um pouco sobre qual nível de aleatoriedade você precisa. Se você está executando um site de poker onde você precisa de níveis criptocharts de aleatoriedade para proteger contra um atacante determinado, você tem requisitos muito diferentes de alguém que quer apenas aleatorizar uma lista de músicas.

Para o shuffling de lista de músicas, não há problema em usar um PRNG semeado (como System.Random). Para um site de poker, não é nem mesmo uma opção e você precisa pensar no problema muito mais difícil do que qualquer um pode fazer por você no stackoverflow. (usar um RNG criptográfico é apenas o começo, você precisa garantir que seu algoritmo não introduza um viés, que você tenha fonts suficientes de entropia e que você não exponha nenhum estado interno que comprometa a aleatoriedade subsequente).

Ok, isso é claramente uma colisão do meu lado (pede desculpas …), mas eu costumo usar um método bastante geral e criptograficamente forte.

 public static class EnumerableExtensions { static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider(); public static IEnumerable Shuffle(this IEnumerable enumerable) { var randomIntegerBuffer = new byte[4]; Func 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 () é uma extensão em qualquer IEnumerable, portanto, obter, digamos, números de 0 a 1000 em ordem aleatória em uma lista pode ser feito com

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

Este método também não dará surpresas quando se trata de ordenação, uma vez que o valor de ordenação é gerado e lembrado exatamente uma vez por elemento na sequência.

Você não precisa de algoritmos complicados.

Apenas uma linha simples:

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

Note que precisamos converter o Array para uma List primeiro, se você não usar List em primeiro lugar.

Além disso, lembre-se de que isso não é eficiente para matrizes muito grandes! Caso contrário, é limpo e simples.

Esta é uma solução completa do console de trabalho com base no exemplo fornecido aqui :

 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 numList = new List(); 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(); 

Esse código embaralha números em uma 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[] 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; } } 

Aqui está uma maneira simples de usar o OLINQ:

 // Input array List lst = new List(); for (int i = 0; i < 500; i += 1) lst.Add(i.ToString()); // Output array List lstRandom = new List(); // 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; }