Как быть уверенным, что случайные числа уникальны и не дублируются? - PullRequest
Новая
       20

Как быть уверенным, что случайные числа уникальны и не дублируются?

2 голосов
/ 04 марта 2012

У меня есть простой код, который генерирует случайные числа 

SecureRandom random = new SecureRandom();
...
public int getRandomNumber(int maxValue) {
    return random.nextInt(maxValue);
}

Вышеприведенный метод вызывается примерно 10 раз (не в цикле).Я хочу убедиться, что все номера уникальны (при условии, что maxValue > 1000).

Могу ли я быть уверен, что буду получать уникальные номера при каждом вызове?Если нет, то как я могу это исправить?

РЕДАКТИРОВАТЬ: Я мог бы сказать это смутно.Я хотел избежать ручных проверок, если я действительно получил уникальные номера, поэтому мне было интересно, есть ли лучшее решение.

Ответы [ 5 ]

5 голосов
/ 04 марта 2012

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

  • Если вы выбираете небольшое количество случайных чисел избольшой диапазон потенциальных чисел, тогда вам, вероятно, лучше всего просто сохранить ранее выбранные числа в наборе и «вручную» проверять наличие дубликатов.Большую часть времени вы фактически не получите дубликат, а тест будет стоить практически без затрат в практическом плане.Это может звучать не элегантно, но на самом деле это не так плохо, как кажется.
  • Некоторые базовые алгоритмы генерации случайных чисел не производят дубликаты на своем «необработанном» уровне.Так, например, алгоритм, называемый генератором XORShift , может эффективно генерировать все числа в пределах определенного диапазона, перемешанные без дубликатов.Таким образом, вы в основном выбираете случайную начальную точку в последовательности, а затем просто генерируете следующие n чисел, и вы знаете, что дубликатов не будет.Но вы не можете произвольно выбрать «max» в этом случае: это должен быть естественный максимум рассматриваемого генератора.

  • Если диапазон возможных чисел мал, но числочисла, которые вам нужно выбрать, находятся в пределах пары порядков величины этого диапазона, тогда вы можете рассматривать это как случайную проблему selection .Например, чтобы выбрать 100 000 чисел в диапазоне 10 000 000 без дубликатов, я могу сделать это:

    Пусть m будет числом выбранных мной случайных чисел

    Для i= От 1 до 10 000 000

    Генерирует случайное число (с плавающей запятой) r в диапазоне 0-1

    If (r <(100 000-m) / (10 000 000-i))), затем добавьте i в список и увеличьте m </p>

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

НоОчевидно, что выбирать последний вариант имеет смысл только в том случае, если вам нужно выбрать достаточно большую долю общего диапазона чисел.Для выбора 10 чисел в диапазоне от 1 до миллиарда вы бы сгенерировали миллиард случайных чисел, когда, просто проверяя наличие дубликатов по ходу дела, вы вряд ли бы получили дубликат и в итоге получили бы только 10 случайных чисел.число.

1 голос
/ 04 марта 2012

Каждый раз, когда вы звоните Random#nextInt(int), вы получаете

псевдослучайное, равномерно распределенное значение типа int между 0 (включительно) и указанным значением (исключая).

Если вы хотите x уникальных номеров, продолжайте получать новые номера, пока у вас их не будет столько, а затем выберите «случайное» число из этого списка.Однако, поскольку вы фильтруете сгенерированные числа, они больше не будут случайными.

1 голос
/ 04 марта 2012

Случайная последовательность не означает, что все значения уникальны. Последовательность 1,1,1,1 точно так же вероятна, как последовательность 712,4,22,424.

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

0 голосов
/ 04 марта 2012

Этот код очень эффективен с процессором за счет памяти. Каждое потенциальное значение стоимости sizeof(int) * maxValue. Целое число без знака будет работать до 65535 как макс. long может использоваться за счет большого объема памяти 2000 байтов для 1000 значений 16-битных целых чисел.

Цель всего массива - сказать, использовали ли вы это значение раньше или нет 1 = yes 'что-нибудь еще = нет 'Цикл while будет генерировать случайные числа, пока не будет найдено уникальное значение. 'после того, как найдено хорошее случайное значение, оно помечает его как использованное и затем возвращает. Будьте осторожны с областью действия переменной a, как если бы она выходила за пределы области видимости, которую ваш массив мог бы стереть. «Я использовал это в c, и это работает. может потребоваться некоторое время, чтобы заставить его работать в Java. 

unsigned int a(1000);

public int getRandomNumber(int maxValue) {
  unsigned int rand;

  while(a(rand)==1) {
    rand=random.nextInt(maxValue);
    if (a(rand)!=1) { a(rand)=1; return rand;}
  }

}
0 голосов
/ 04 марта 2012

Для такого небольшого числа возможных значений тривиальная реализация будет состоять в том, чтобы поместить ваши 1000 целых чисел в список и иметь цикл, который на каждой итерации генерирует случайное число от 0 до list.size(), выбирая числосохраните этот индекс и удалите его из списка.

...