Gere N números randoms e exclusivos dentro de um intervalo

O que é uma maneira eficiente de gerar N números únicos dentro de um determinado intervalo usando C #? Por exemplo, gere 6 números únicos entre 1 e 50. Uma maneira preguiçosa seria simplesmente usar Random.Next() em um loop e armazenar esse número em uma matriz / lista, depois repetir e verificar se já existe ou não, etc. Existe uma maneira melhor de gerar um grupo de números randoms, mas únicos? Para adicionar mais contexto, gostaria de selecionar N itens randoms de uma coleção, usando o índice deles.

obrigado

    Pegue uma matriz de 50 elementos: {1, 2, 3, .... 50} Embaralhe a matriz usando qualquer um dos algoritmos padrão de arrays aleatoriamente randoms. Os primeiros seis elementos da matriz modificada são o que você está procurando. HTH

    Para 6-de-50, não estou muito certo de que me preocuparia com a eficiência, uma vez que a chance de uma duplicata é relativamente baixa (30% no total, a partir dos meus cálculos de back-of-the-envelope). Você poderia muito facilmente lembrar os números anteriores que você gerou e jogá-los fora, algo como (pseudo-código):

     n[0] = rnd(50) for each i in 1..5: n[i] = n[0] while n[1] == n[0]: n[1] = rnd(50) while n[2] == any of (n[0], n[1]): n[2] = rnd(50) while n[3] == any of (n[0], n[1], n[2]): n[3] = rnd(50) while n[4] == any of (n[0], n[1], n[2], n[3]): n[4] = rnd(50) while n[5] == any of (n[0], n[1], n[2], n[3], n[4]): n[5] = rnd(50) 

    No entanto, isso será quebrado à medida que você passa de 6-de-50 para 48-de-50 ou 6-de-6, já que as duplicatas começam a ficar muito mais prováveis. Isso porque o pool de números disponíveis fica menor e você acaba jogando fora cada vez mais.

    Para uma solução muito eficiente que lhe dá um subconjunto de seus valores com possibilidade zero de duplicatas (e sem ordenação prévia desnecessária), Fisher-Yates é o caminho a percorrer.

     dim n[50] // gives n[0] through n[9] for each i in 0..49: n[i] = i // initialise them to their indexes nsize = 50 // starting pool size do 6 times: i = rnd(nsize) // give a number between 0 and nsize-1 print n[i] nsize = nsize - 1 // these two lines effectively remove the used number n[i] = n[nsize] 

    Simplesmente selecionando um número random do pool, substituindo-o pelo número superior daquele pool, reduzindo o tamanho do pool, você recebe um shuffle sem precisar se preocupar com um grande número de swaps na frente.

    Isso é importante se o número for alto, pois não introduz um atraso de boot desnecessário.

    Por exemplo, examine a seguinte verificação de banco, escolhendo 10-de-10:

     <------ n[] ------> 0 1 2 3 4 5 6 7 8 9 nsize rnd(nsize) output ------------------- ----- ---------- ------ 0 1 2 3 4 5 6 7 8 9 10 4 4 0 1 2 3 9 5 6 7 8 9 7 7 0 1 2 3 9 5 6 8 8 2 2 0 1 8 3 9 5 6 7 6 6 0 1 8 3 9 5 6 0 0 5 1 8 3 9 5 2 8 5 1 9 3 4 1 1 5 3 9 3 0 5 9 3 2 1 3 9 1 0 9 

    Você pode ver a piscina diminuindo à medida que avança e, porque você está sempre substituindo a usada por uma não utilizada, você nunca mais terá uma repetição.

    Usar os resultados retornados disso como índices em sua coleção garantirá que nenhum item duplicado será selecionado.

    Para grandes conjuntos de números exclusivos, coloque-os em uma lista.

      Random random = new Random(); List uniqueInts = new List(10000); List ranInts = new List(500); for (int i = 1; i < 10000; i++) { uniqueInts.Add(i); } for (int i = 1; i < 500; i++) { int index = random.Next(uniqueInts.Count) + 1; ranInts.Add(uniqueInts[index]); uniqueInts.RemoveAt(index); } 

    Em seguida, gere aleatoriamente um número de 1 para myInts.Count. Armazene o valor myInt e remova-o da lista. Não há necessidade de embaralhar a lista nem verificar se o valor já existe.

     var random = new Random(); var intArray = Enumerable.Range(0, 4).OrderBy(t => random.Next()).ToArray(); 

    Esta matriz irá conter 5 números randoms de 0 a 4.

    ou

      var intArray = Enumerable.Range(0, 10).OrderBy(t => random.Next()).Take(5).ToArray(); 

    Este array irá conter 5 números randoms entre 0 e 10.

     int firstNumber = intArray[0]; int secondNumber = intArray[1]; int thirdNumber = intArray[2]; int fourthNumber = intArray[3]; int fifthNumber = intArray[4]; 

    em vez de usar List use Dictionary !!

    Caso isso ajude alguém, prefiro alocar o número mínimo de itens necessários. Abaixo, faço uso de um HashSet, que garante que novos itens sejam exclusivos. Isso também deve funcionar com collections muito grandes, até os limites do que o HashSet faz bem.

      public static IEnumerable GetRandomNumbers(int numValues, int maxVal) { var rand = new Random(); var yieldedValues = new HashSet(); int counter = 0; while (counter < numValues) { var r = rand.Next(maxVal); if (yieldedValues.Add(r)) { counter++; yield return r; } } } 

    gerar números randoms únicos de 1 a 40:

    saída confirmada:

     class Program { static int[] a = new int[40]; static Random r = new Random(); static bool b; static void Main(string[] args) { int t; for (int i = 0; i < 20; i++) { lab: t = r.Next(1, 40); for(int j=0;j<20;j++) { if (a[j] == t) { goto lab; } } a[i] = t; Console.WriteLine(a[i]); } Console.Read(); } } 

    exemplo de saída:

    7 38 14 18 13 29 28 26 22 8 24 19 35 39 33 32 20 2 15 37