Melhor maneira de embaralhar um array com .NET
https://stackoverflow.com/questions/108819
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
O que é a melhor maneira de randomize uma matriz de strings com .NET? Minha matriz contém cerca de 500 cordas e eu gostaria de criar um novo Array com as mesmas cordas, mas em uma ordem aleatória.
Por favor, inclua um exemplo C #, em sua resposta.
Solução
Se você estiver em .NET 3.5, você pode usar o seguinte frieza IEnumerable (VB.NET, C # não, mas a idéia deve ser claro ...):
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()).ToArray()
Segundo editar, em resposta às observações que System.Random "não é threadsafe" e "adequado apenas para aplicativos de brinquedo", devido ao retornar uma seqüência com base no tempo: como usado no meu exemplo, Random () é perfeitamente thread seguro, a menos que você está permitindo que a rotina em que você embaralhar a matriz para ser re-entrou, caso em que você vai precisar de algo como lock (MyRandomArray) qualquer maneira para não corromper seus dados, o que irá proteger rnd também.
Além disso, ele deve ser bem entendido que System.Random como uma fonte de entropia não é muito forte. Como observado na MSDN documentação , você deve usar algo derivado System.Security.Cryptography.RandomNumberGenerator se você estiver fazendo a segurança relacionadas com qualquer coisa. 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]);
}
Outras dicas
A seguir implementação usa o Fisher-Yates algoritmo AKA o Knuth shuffle. Corre-se em O (n) de tempo e baralha no lugar, assim é melhor desempenho do que os 'ordenado por aleatório' técnica, embora seja mais linhas de código. Consulte aqui para algumas medições de desempenho comparativos. Eu tenho usado System.Random, o que é bom para fins não criptográficas. *
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 matrizes mais longas, a fim de fazer o número (extremamente grande) de permutações igualmente prováveis ??seria necessário para executar um gerador de números pseudo-aleatório (PRNG) através de muitas iterações para cada troca de produzir entropia suficiente. Para uma matriz de 500 elementos apenas uma pequena fração do possível 500! 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 como o RNG que utiliza.
Você está procurando um algoritmo de embaralhamento, certo?
Ok, há duas maneiras de fazer isso: os inteligentes-mas-pessoas-sempre-parecem-to-misunderstand-it-e-get-it-wrong-so-talvez-its-not-que-clever- pós-tudo maneira, e os mudos-as-rochas-mas-que-cuidados, porque-lo da fábrica caminho.
maneira mudo
- Criar uma cópia de sua primeira matriz, mas tag cada corda deve com um número aleatório.
- Classificar a matriz duplicado em relação ao número aleatório.
Este algoritmo funciona bem, mas certifique-se de que seu gerador de números aleatórios é improvável que a tag duas cordas com o mesmo número. Por causa do chamado aniversário Paradox , isso acontece mais frequentemente do que se poderia esperar. Sua complexidade de tempo é O ( n log n ).
inteligente maneira
vou descrever isso como um algoritmo recursivo:
Para misturar uma matriz de tamanho n (Índices no intervalo [0 ..
se n = 0n -1]): se n > 0
- não fazer nada
- (passo recursiva) embaralhar o primeiro
n -1 elementos da matriz - escolher um índice aleatória, x , no intervalo de [0 ..
n -1] - trocar o elemento no índice
n -1 com o elemento no índice x
O equivalente iterativa é caminhar uma iteração através da matriz, trocando com elementos aleatórios como você ir junto, mas aviso que você não pode swap com um elemento depois o que o iterador aponta para. Este é um erro muito comum, e leva a uma reprodução aleatória tendencioso.
Complexidade de tempo é O ( n ).
Este algoritmo é simples, mas não é eficiente, O (N 2 ). Todo o "ordem por" algoritmos são tipicamente de O (N log N). Ele provavelmente não faz uma diferença inferior a centenas de milhares de elementos, mas que seria 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);
}
A razão por que é O (N 2 ) é sutil: List.RemoveAt () é uma operação de o (N), a menos que remover de forma a partir da extremidade.
Você também pode fazer um método de extensão para fora do Matt Howells. Exemplo.
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;
}
}
}
}
Em seguida, você pode simplesmente 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<string>();
Randomizing a matriz é intensivo como você tem que mudar em torno de um monte de cordas. Por que não ler apenas aleatoriamente a partir da matriz? Na pior das hipóteses você poderia até criar uma classe de invólucro com um getNextString (). Se você realmente precisa fazer para criar uma matriz aleatória, em seguida, você poderia fazer algo como
for i = 0 -> i= array.length * 5
swap two strings in random places
A * 5 é arbitrária.
Apenas pensar em cima da minha cabeça, você poderia fazer isso:
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);
}
Gerar uma variedade de carros alegóricos aleatórios ou ints do mesmo comprimento. Ordenar essa matriz, e fazer swaps correspondentes em seu matriz de destino.
Isso resulta uma espécie verdadeiramente independente.
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, sua solução ising uma IComparer personalizado não é seguro. O tipo rotinas exigem o comparador de se conformar com vários requisitos, a fim de funcionar corretamente. Primeiro entre eles é a consistência. Se o comparador é chamado no mesmo par de objetos, ele deve retornar sempre o mesmo resultado. (A comparação também deve ser transitivo).
O não cumprimento destes requisitos pode causar uma série de problemas na rotina de classificação incluindo a possibilidade de um loop infinito.
Em relação às soluções que associam um valor numérico aleatório com cada entrada e, em seguida, ordenar por esse valor, estes são levados a um viés inerente na saída, porque qualquer momento duas entradas são atribuídos o mesmo valor numérico, a aleatoriedade da vontade de saída ser comprometida. (Em um "estável" espécie de rotina, o que ocorrer primeiro na entrada será a primeira na saída. Array.Sort não acontece para ser estável, mas ainda há um preconceito baseado no particionamento feito pelo algoritmo Quicksort).
Você precisa fazer algumas reflexões sobre o nível de aleatoriedade que você necessita. Se você estiver executando um site de poker onde você precisa de níveis de criptografia de aleatoriedade para proteger contra um atacante determinado você tem requisitos muito diferente de alguém que só quer embaralhar uma lista de reprodução de música.
Para-lista de músicas baralhar, não há problema usando um PRNG semeado (como System.Random). Para um site de poker, não é sequer uma opção e você precisa pensar sobre o problema muito mais difícil do que ninguém vai fazer por você em stackoverflow. (Usando um RNG criptográfico é apenas o começo, você precisa garantir que o seu algoritmo não introduzir um viés, que você tem fontes suficientes de entropia, e que você não exponha qualquer estado interno que possa comprometer a aleatoriedade subsequente).
Este post já foi muito bem atendida - usar uma implementação Durstenfeld de shuffle Fisher-Yates para um rápido e resultado imparcial. Houve mesmo algumas implementações postou, embora noto alguns são realmente incorreta.
Eu escrevi um par de posts um tempo atrás sobre implementação embaralha integrais e parciais usando este técnica, e (esta segunda ligação é onde eu estou esperando para agregar valor) também um post de acompanhamento sobre como verificar se a sua implementação é imparciais, que podem ser utilizados para verificar qualquer algoritmo shuffle. Você pode ver no final do segundo pós o efeito de um simples erro na seleção de números aleatórios pode fazer.
Ok, esta é claramente uma colisão do meu lado (se desculpa ...), mas muitas vezes eu uso um método bastante geral e criptograficamente forte.
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;
}
}
Aleatório () é uma extensão em qualquer IEnumerable assim que começar, por exemplo, 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 vai dar qualquer surpresas quando se trata de classificar, já que o valor tipo é gerado e lembrava exatamente uma vez por elemento na seqüência.
Você não precisa de algoritmos complicados.
Apenas uma simples linha:
Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();
Note que precisamos converter o Array a um List primeiro lugar, se você não usar List em primeiro lugar.
Além disso, mente que este não é eficiente para matrizes muito grandes! Caso contrário, é limpo e simples.
Esta é uma solução Console de trabalho completo baseado em o 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<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();
Este baralha código 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>(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 usando 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;
}
