Уникальные (неповторяющиеся) случайные числа в O (1)?

Question

Я хотел бы генерировать уникальные случайные числа от 0 до 1000, которые никогда не повторяются (то есть 6 не появляется дважды), но это не прибегает к чему-то вроде поиска O (N) предыдущих значений, чтобы сделать Это. Возможно ли это?

Answer 1

Инициализируйте массив из 1001 целого числа со значениями 0-1000 и установите переменную max для текущего максимального индекса массива (начиная с 1000). Выберите случайное число r в диапазоне от 0 до max, поменяйте местами число в позиции r и число в положении max и верните число теперь в положение max. Уменьшите максимум на 1 и продолжайте. Когда max равно 0, верните max обратно к размеру массива - 1 и начните заново без необходимости повторной инициализации массива.

Обновление: Хотя я придумал этот метод самостоятельно, когда ответил на вопрос, после некоторых исследований я понял, что это модифицированная версия Фишера-Йетса , известная как Дюрстенфельд-Фишер-Йейтс или Кнут-Фишер-Йейтс. Поскольку описанию может быть немного сложно следовать, я привел пример ниже (используя 11 элементов вместо 1001):

Массив начинается с 11 элементов, инициализированных в массив [n] = n, max начинается с 10:

+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
                                ^
                               max    

На каждой итерации случайное число r выбирается между 0 и max, массив [r] и массив [max] меняются местами, возвращается новый массив [max] и значение max уменьшается:

max = 10, r = 3
           +--------------------+
           v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                       +-----+
                       v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
     +--------------------+
     v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
                 +-----+
                 v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

...

После 11 итераций все числа в массиве были выбраны, max == 0, и элементы массива перетасовываются:

+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

На этом этапе max можно сбросить до 10, и процесс можно продолжить.

Answer 2

Вы можете сделать это:

1. Создать список, 0..1000.
2. Перемешать список. (См. Фишер-Йейтс shuffle , чтобы найти хороший способ сделать это)
3. Возвращать числа по порядку из перемешанного списка.

Так что для этого не требуется каждый раз искать старые значения, но все равно требуется O (N) для начального перемешивания. Но, как отметил Нильс в комментариях, это амортизируется O (1).

Answer 3

Использовать регистр сдвига максимальной линейной обратной связи .

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

Answer 4

Вы можете использовать линейный конгруэнтный генератор . Где m (модуль) будет ближайшим простым числом больше 1000. Когда вы выберете число из диапазона, просто получите следующее. Последовательность будет повторяться только после того, как все элементы будут выполнены, и вам не нужно будет использовать таблицу. Знайте о недостатках этого генератора (включая отсутствие случайности).

Answer 5

Вы можете использовать Форматно-сохраняющее шифрование для шифрования счетчика. Ваш счетчик просто идет от 0 вверх, и шифрование использует ключ по вашему выбору, чтобы превратить его в, казалось бы, случайное значение любого желаемого значения радиуса и ширины. Например. для примера в этом вопросе: основание 10, ширина 3.

Блочные шифры обычно имеют фиксированный размер блока, например 64 или 128 бит. Но шифрование, сохраняющее формат, позволяет вам взять стандартный шифр, такой как AES, и сделать шифр меньшей ширины, любого желаемого радиуса и ширины, с алгоритмом, который все еще криптографически устойчив.

Гарантируется, что никогда не будет коллизий (поскольку криптографические алгоритмы создают отображение 1: 1). Он также обратим (двухстороннее сопоставление), поэтому вы можете взять полученное число и вернуться к значению счетчика, с которого вы начали.

Этот метод не требует памяти для хранения перетасованного массива и т. Д., Что может быть преимуществом в системах с ограниченной памятью.

AES-FFX является одним из предложенных стандартных методов для достижения этой цели. Я экспериментировал с некоторым базовым кодом Python, который основан на идее AES-FFX, хотя и не полностью соответствует - см. Код Python здесь . Это может, например, зашифруйте счетчик случайным 7-значным десятичным числом или 16-разрядным числом. Вот пример радиуса 10, ширина 3 (чтобы дать число от 0 до 999 включительно) в качестве поставленного вопроса:

000   733
001   374
002   882
003   684
004   593
005   578
006   233
007   811
008   072
009   337
010   119
011   103
012   797
013   257
014   932
015   433
...   ...

Чтобы получить разные неповторяющиеся псевдослучайные последовательности, измените ключ шифрования. Каждый ключ шифрования создает свою неповторяющуюся псевдослучайную последовательность.

Answer 6

Для младших чисел, таких как 0 ... 1000, создать список, содержащий все числа, и перетасовывать его просто. Но если набор чисел для рисования очень большой, есть другой элегантный способ: вы можете построить псевдослучайную перестановку, используя ключ и криптографическую хеш-функцию. Смотрите следующий C ++ - ish пример псевдокода:

unsigned randperm(string key, unsigned bits, unsigned index) {
  unsigned half1 =  bits    / 2;
  unsigned half2 = (bits+1) / 2;
  unsigned mask1 = (1 << half1) - 1;
  unsigned mask2 = (1 << half2) - 1;
  for (int round=0; round<5; ++round) {
    unsigned temp = (index >> half1);
    temp = (temp << 4) + round;
    index ^= hash( key + "/" + int2str(temp) ) & mask1;
    index = ((index & mask2) << half1) | ((index >> half2) & mask1);
  }
  return index;
}

Здесь hash - это просто произвольная псевдослучайная функция, которая отображает строку символов в возможно огромное целое число без знака. Функция randperm представляет собой перестановку всех чисел в пределах 0 ... pow (2, бит) -1, предполагая фиксированный ключ. Это следует из конструкции, потому что каждый шаг, который изменяет переменную index, является обратимым. Это вдохновлено шифром Фейстеля .

Answer 7

Вы можете использовать мой алгоритм Xincrol, описанный здесь:

http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html

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

Последняя версия также позволяет установить диапазон чисел, например, если я хочу уникальные случайные числа в диапазоне 0-1073741821.

Я практически использовал его для

• MP3-плеер, который воспроизводит каждую песню случайным образом, но только один раз для каждого альбома / каталога
• Эффект растворения пикселей в пикселях (быстрый и плавный)
• Создание секретного «шумового» тумана над изображением для подписей и маркеров (стеганография)
• Идентификаторы объектов данных для сериализации огромного количества объектов Java через базы данных
• Защита битов Triple Majority
• Шифрование адреса + значения (каждый байт не только зашифрован, но и перемещен в новое зашифрованное место в буфере). Это действительно разозлило на меня сотрудников криптоанализа: -)
• Обычный текст для простого шифрования. Шифрование текста для SMS, электронной почты и т. Д.
• Мой Техасский Холдем Покерный Калькулятор (THC)
• Несколько моих игр для симуляции, "перетасовки", рейтинг
• более

Открыто, бесплатно. Попробуйте ...

Answer 8

Вам даже не нужен массив для его решения.

Вам нужна битовая маска и счетчик.

Инициализировать счетчик на ноль и увеличивать его при последующих вызовах. XOR счетчик с битовой маской (случайно выбранной при запуске или фиксированной) для генерации псевдослучайного числа Если вы не можете иметь числа, превышающие 1000, не используйте битовую маску шире, чем 9 бит. (Другими словами, битовая маска является целым числом не выше 511.)

Убедитесь, что когда счетчик проходит 1000, вы обнуляете его. В это время вы можете выбрать другую случайную битовую маску & mdash; если вам нравится & mdash; производить одинаковый набор чисел в другом порядке.

Answer 9

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

#!/usr/bin/perl

($top, $n) = @ARGV; # generate $n integer numbers in [0, $top)

$last = -1;
for $i (0 .. $n-1) {
    $range = $top - $n + $i - $last;
    $r = 1 - rand(1.0)**(1 / ($n - $i));
    $last += int($r * $range + 1);
    print "$last ($r)\n";
}

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

Answer 10

Вот код, который я набрал, который использует логику первого решения. Я знаю, что это «не зависит от языка», но просто хотел представить это в качестве примера на C # на тот случай, если кто-то ищет быстрое практическое решение.

// Initialize variables
Random RandomClass = new Random();
int RandArrayNum;
int MaxNumber = 10;
int LastNumInArray;
int PickedNumInArray;
int[] OrderedArray = new int[MaxNumber];      // Ordered Array - set
int[] ShuffledArray = new int[MaxNumber];     // Shuffled Array - not set

// Populate the Ordered Array
for (int i = 0; i < MaxNumber; i++)                  
{
    OrderedArray[i] = i;
    listBox1.Items.Add(OrderedArray[i]);
}

// Execute the Shuffle                
for (int i = MaxNumber - 1; i > 0; i--)
{
    RandArrayNum = RandomClass.Next(i + 1);         // Save random #
    ShuffledArray[i] = OrderedArray[RandArrayNum];  // Populting the array in reverse
    LastNumInArray = OrderedArray[i];               // Save Last Number in Test array
    PickedNumInArray = OrderedArray[RandArrayNum];  // Save Picked Random #
    OrderedArray[i] = PickedNumInArray;             // The number is now moved to the back end
    OrderedArray[RandArrayNum] = LastNumInArray;    // The picked number is moved into position
}

for (int i = 0; i < MaxNumber; i++)                  
{
    listBox2.Items.Add(ShuffledArray[i]);
}