Генерация N случайных и уникальных чисел в диапазоне

Question

Каков эффективный способ генерации N уникальных чисел в заданном диапазоне с использованием C #? Например, сгенерируйте 6 уникальных чисел от 1 до 50. Ленивым способом было бы просто использовать Random.Next() в цикле и сохранить это число в массиве / списке, затем повторить и проверить, существует ли оно уже или нет и т. Д. Есть ли лучший способ создать группу случайных, но уникальных чисел? Чтобы добавить больше контекста, я хотел бы выбрать N случайных элементов из коллекции, используя их индекс.

спасибо

Answer 1

Взять массив из 50 элементов: {1, 2, 3, .... 50} Перемешать массив, используя любой из стандартных алгоритмов случайного перемешивания массивов. Первые шесть элементов модифицированного массива - это то, что вы ищете. НТН

Answer 2

Для 6 из 50 я не слишком уверен, что буду беспокоиться об эффективности, поскольку вероятность дублирования относительно невелика (всего 30%, по моим подсчетам за пределами конверта).Вы можете довольно легко просто вспомнить предыдущие сгенерированные вами числа и выбросить их, что-то вроде (псевдокод):

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)

Однако, это сломается, когда вы перейдете с 6 на 50до 48 из 50 или 6 из 6, поскольку дубликаты начинают становиться более вероятными далеко .Это потому, что пул доступных чисел становится меньше, и вы в конечном итоге выбрасываете все больше и больше.

Для очень эффективного решения, которое дает вам подмножество ваших значений с ноль возможностью дублирования (и никакой ненужной предварительной сортировки), Fisher-Yates - это путь.

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]

Просто выберите случайное число из пула, заменив его на верхнее число из этого пула, затем уменьшивразмер пула, вы получаете случайное перемешивание, не беспокоясь о большом количестве перестановок впереди.

Это важно, если число велико, поскольку оно не приводит к ненужной задержке запуска.

Например, рассмотрите следующий бенч-тест, выбрав 10-из-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

Вы можете видеть, как пул сокращается по ходу и потому, что вы всегда заменяете использованный.с неиспользованным, у вас никогда не будет повторения.

Использование результатов, полученных из этого в качестве индексов в вашей коллекции, гарантирует, что дубликат не будетэлементы будут выбраны.

Answer 3

Для больших наборов уникальных чисел поместите их в список.

        Random random = new Random();
        List<int> uniqueInts = new List<int>(10000);
        List<int> ranInts = new List<int>(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);
        }

Затем случайным образом сгенерируйте число от 1 до myInts.Count. Сохраните значение myInt и удалите его из списка. Нет необходимости перетасовывать список и искать, если значение уже существует.

Answer 4

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

Этот массив будет содержать 5 случайных чисел от 0 до 4.

или

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

Этот массив будет содержать 5 случайных чисел от 0 до 10.

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

Answer 5

вместо использования List используйте Dictionary !!

Answer 6

Если кому-то это поможет, я предпочитаю выделять минимальное количество необходимых предметов.Ниже я использую HashSet, который гарантирует, что новые элементы уникальны.Это должно работать и с очень большими коллекциями, вплоть до того, с чем хорошо работает HashSet.

    public static IEnumerable<int> GetRandomNumbers(int numValues, int maxVal)
    {
        var rand = new Random();
        var yieldedValues = new HashSet<int>();

        int counter = 0;
        while (counter < numValues)
        {
            var r = rand.Next(maxVal);
            if (yieldedValues.Add(r))
            {
                counter++;
                yield return r;
            }
        }
    }

Answer 7

генерирует уникальные случайные числа от 1 до 40:

вывод подтвержден:

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


}

образец вывода:

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