Уникальные (неповторяющиеся) случайные числа в O(1)?
Я хотел бы генерировать уникальные случайные числа от 0 до 1000, которые никогда не повторяются (т.е. 6 не появляется дважды), но это не прибегает к чему-то вроде поиска O(N) предыдущих значений, чтобы сделать это. Это возможно?
21 ответ
Инициализируйте массив из 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, и процесс можно продолжить.
Вы можете сделать это:
- Создайте список, 0..1000.
- Перемешать список (См. Fisher-Yates shuffle для хорошего способа сделать это.)
- Вернуть номера по порядку из перемешанного списка.
Так что это не требует поиска старых значений каждый раз, но все равно требует O(N) для начального перемешивания. Но, как отметил Нильс в комментариях, это амортизированный O(1).
Используйте максимальный регистр сдвига с линейной обратной связью.
Это реализуемо в нескольких строках C и во время выполнения выполняет всего несколько тестов / веток, небольшое добавление и сдвиг битов. Это не случайно, но это обманывает большинство людей.
Вы можете использовать шифрование с сохранением формата для шифрования счетчика. Ваш счетчик просто идет от 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
... ...
Чтобы получить разные неповторяющиеся псевдослучайные последовательности, измените ключ шифрования. Каждый ключ шифрования создает различную неповторяющуюся псевдослучайную последовательность.
Вы можете использовать линейный конгруэнтный генератор. куда m (модуль) будет ближайшим простым числом больше 1000. Когда вы выберете число из диапазона, просто получите следующее. Последовательность будет повторяться только после того, как все элементы будут выполнены, и вам не нужно будет использовать таблицу. Имейте в виду недостатки этого генератора (в том числе отсутствие случайности).
Я думаю, что линейный конгруэнтный генератор будет самым простым решением.
и есть только 3 ограничения на значения a, c и m
- m и c относительно простые,
- а-1 делится на все простые множители м
- a-1 делится на 4, если m делится на 4
PS метод уже упоминался, но пост содержит неверные предположения о постоянных значениях. Константы ниже должны нормально работать для вашего случая
В вашем случае вы можете использовать a = 1002, c = 757, m = 1001
X = (1002 * X + 757) mod 1001
Для младших чисел, таких как 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 обратим. Это вдохновлено шифром Фейстеля.
Вы можете использовать мой алгоритм Xincrol, описанный здесь:
http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html
Это чисто алгоритмический метод генерации случайных, но уникальных чисел без массивов, списков, перестановок или большой загрузки процессора.
Последняя версия позволяет также установить диапазон чисел, например, если я хочу уникальные случайные числа в диапазоне 0-1073741821.
Я практически использовал его для
- MP3-плеер, который воспроизводит каждую песню случайным образом, но только один раз для альбома / каталога
- Эффект растворения пикселей в пикселях (быстрый и плавный)
- Создание секретного "шумового" тумана над изображением для подписей и маркеров (стеганография)
- Идентификаторы объектов данных для сериализации огромного количества объектов Java через базы данных
- Защита битов памяти Triple Majority
- Шифрование адреса + значения (каждый байт не только зашифрован, но и перемещен в новое зашифрованное место в буфере). Это действительно разозлило на меня сотрудников криптоанализа:-)
- Простое преобразование текста в обычное шифрование, шифрование текста для SMS, электронной почты и т. Д.
- Мой Техасский Холдем Покерный Калькулятор (THC)
- Несколько моих игр для симуляторов, "тасования", рейтинга
- Больше
Это открыто, бесплатно. Попробуйте...
Вам даже не нужен массив, чтобы решить этот.
Вам нужна битовая маска и счетчик.
Инициализируйте счетчик на ноль и увеличивайте его при последующих вызовах. XOR счетчик с битовой маской (случайно выбранной при запуске или фиксированной) для генерации псевдослучайного числа. Если вы не можете иметь числа, превышающие 1000, не используйте битовую маску шире, чем 9 бит. (Другими словами, битовая маска является целым числом не выше 511.)
Убедитесь, что когда счетчик проходит 1000, вы обнуляете его. В это время вы можете выбрать другую случайную битовую маску - если хотите - чтобы создать тот же набор чисел в другом порядке.
Результаты этого метода соответствуют, когда предел велик, и вы хотите сгенерировать только несколько случайных чисел.
#!/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";
}
Обратите внимание, что числа генерируются в порядке возрастания, но затем вы можете перемешать их.
Вопрос " Как эффективно сгенерировать список из K неповторяющихся целых чисел от 0 до верхней границы N связан как дубликат, и если вам нужно что-то, что является O(1) на сгенерированное случайное число (без O(n)") стоимость запуска)) есть простой твик принятого ответа.
Создайте пустую неупорядоченную карту (пустая упорядоченная карта будет принимать O(log k) на элемент) от целого к целому - вместо использования инициализированного массива. Установите максимум на 1000, если это максимум,
- Выберите случайное число r от 0 до макс.
- Убедитесь, что оба элемента карты r и max существуют в неупорядоченной карте. Если они не существуют, создайте их со значением, равным их индексу.
- Поменяйте местами элементы r и max
- Верните элемент max и уменьшите max на 1 (если max становится отрицательным, все готово).
- Вернуться к шагу 1.
Единственное отличие по сравнению с использованием инициализированного массива состоит в том, что инициализация элементов откладывается / пропускается, но она будет генерировать точно такие же числа из одного и того же PRNG.
Вот код, который я набрал, который использует логику первого решения. Я знаю, что это "не зависит от языка", но просто хотел представить это в качестве примера на 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]);
}
Вот пример кода COBOL, с которым вы можете поиграть.
Я могу отправить вам файл RANDGEN.exe, чтобы вы могли поиграть с ним, чтобы узнать, хочет ли он этого.
IDENTIFICATION DIVISION.
PROGRAM-ID. RANDGEN as "ConsoleApplication2.RANDGEN".
AUTHOR. Myron D Denson.
DATE-COMPILED.
* **************************************************************
* SUBROUTINE TO GENERATE RANDOM NUMBERS THAT ARE GREATER THAN
* ZERO AND LESS OR EQUAL TO THE RANDOM NUMBERS NEEDED WITH NO
* DUPLICATIONS. (CALL "RANDGEN" USING RANDGEN-AREA.)
*
* CALLING PROGRAM MUST HAVE A COMPARABLE LINKAGE SECTION
* AND SET 3 VARIABLES PRIOR TO THE FIRST CALL IN RANDGEN-AREA
*
* FORMULA CYCLES THROUGH EVERY NUMBER OF 2X2 ONLY ONCE.
* RANDOM-NUMBERS FROM 1 TO RANDOM-NUMBERS-NEEDED ARE CREATED
* AND PASSED BACK TO YOU.
*
* RULES TO USE RANDGEN:
*
* RANDOM-NUMBERS-NEEDED > ZERO
*
* COUNT-OF-ACCESSES MUST = ZERO FIRST TIME CALLED.
*
* RANDOM-NUMBER = ZERO, WILL BUILD A SEED FOR YOU
* WHEN COUNT-OF-ACCESSES IS ALSO = 0
*
* RANDOM-NUMBER NOT = ZERO, WILL BE NEXT SEED FOR RANDGEN
* (RANDOM-NUMBER MUST BE <= RANDOM-NUMBERS-NEEDED)
*
* YOU CAN PASS RANDGEN YOUR OWN RANDOM-NUMBER SEED
* THE FIRST TIME YOU USE RANDGEN.
*
* BY PLACING A NUMBER IN RANDOM-NUMBER FIELD
* THAT FOLLOWES THESE SIMPLE RULES:
* IF COUNT-OF-ACCESSES = ZERO AND
* RANDOM-NUMBER > ZERO AND
* RANDOM-NUMBER <= RANDOM-NUMBERS-NEEDED
*
* YOU CAN LET RANDGEN BUILD A SEED FOR YOU
*
* THAT FOLLOWES THESE SIMPLE RULES:
* IF COUNT-OF-ACCESSES = ZERO AND
* RANDOM-NUMBER = ZERO AND
* RANDOM-NUMBER-NEEDED > ZERO
*
* TO INSURING A DIFFERENT PATTERN OF RANDOM NUMBERS
* A LOW-RANGE AND HIGH-RANGE IS USED TO BUILD
* RANDOM NUMBERS.
* COMPUTE LOW-RANGE =
* ((SECONDS * HOURS * MINUTES * MS) / 3).
* A HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE
* AFTER RANDOM-NUMBER-BUILT IS CREATED
* AND IS BETWEEN LOW AND HIGH RANGE
* RANDUM-NUMBER = RANDOM-NUMBER-BUILT - LOW-RANGE
*
* **************************************************************
ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
DATA DIVISION.
FILE SECTION.
WORKING-STORAGE SECTION.
01 WORK-AREA.
05 X2-POWER PIC 9 VALUE 2.
05 2X2 PIC 9(12) VALUE 2 COMP-3.
05 RANDOM-NUMBER-BUILT PIC 9(12) COMP.
05 FIRST-PART PIC 9(12) COMP.
05 WORKING-NUMBER PIC 9(12) COMP.
05 LOW-RANGE PIC 9(12) VALUE ZERO.
05 HIGH-RANGE PIC 9(12) VALUE ZERO.
05 YOU-PROVIDE-SEED PIC X VALUE SPACE.
05 RUN-AGAIN PIC X VALUE SPACE.
05 PAUSE-FOR-A-SECOND PIC X VALUE SPACE.
01 SEED-TIME.
05 HOURS PIC 99.
05 MINUTES PIC 99.
05 SECONDS PIC 99.
05 MS PIC 99.
*
* LINKAGE SECTION.
* Not used during testing
01 RANDGEN-AREA.
05 COUNT-OF-ACCESSES PIC 9(12) VALUE ZERO.
05 RANDOM-NUMBERS-NEEDED PIC 9(12) VALUE ZERO.
05 RANDOM-NUMBER PIC 9(12) VALUE ZERO.
05 RANDOM-MSG PIC X(60) VALUE SPACE.
*
* PROCEDURE DIVISION USING RANDGEN-AREA.
* Not used during testing
*
PROCEDURE DIVISION.
100-RANDGEN-EDIT-HOUSEKEEPING.
MOVE SPACE TO RANDOM-MSG.
IF RANDOM-NUMBERS-NEEDED = ZERO
DISPLAY 'RANDOM-NUMBERS-NEEDED ' NO ADVANCING
ACCEPT RANDOM-NUMBERS-NEEDED.
IF RANDOM-NUMBERS-NEEDED NOT NUMERIC
MOVE 'RANDOM-NUMBERS-NEEDED NOT NUMERIC' TO RANDOM-MSG
GO TO 900-EXIT-RANDGEN.
IF RANDOM-NUMBERS-NEEDED = ZERO
MOVE 'RANDOM-NUMBERS-NEEDED = ZERO' TO RANDOM-MSG
GO TO 900-EXIT-RANDGEN.
IF COUNT-OF-ACCESSES NOT NUMERIC
MOVE 'COUNT-OF-ACCESSES NOT NUMERIC' TO RANDOM-MSG
GO TO 900-EXIT-RANDGEN.
IF COUNT-OF-ACCESSES GREATER THAN RANDOM-NUMBERS-NEEDED
MOVE 'COUNT-OF-ACCESSES > THAT RANDOM-NUMBERS-NEEDED'
TO RANDOM-MSG
GO TO 900-EXIT-RANDGEN.
IF YOU-PROVIDE-SEED = SPACE AND RANDOM-NUMBER = ZERO
DISPLAY 'DO YOU WANT TO PROVIDE SEED Y OR N: '
NO ADVANCING
ACCEPT YOU-PROVIDE-SEED.
IF RANDOM-NUMBER = ZERO AND
(YOU-PROVIDE-SEED = 'Y' OR 'y')
DISPLAY 'ENTER SEED ' NO ADVANCING
ACCEPT RANDOM-NUMBER.
IF RANDOM-NUMBER NOT NUMERIC
MOVE 'RANDOM-NUMBER NOT NUMERIC' TO RANDOM-MSG
GO TO 900-EXIT-RANDGEN.
200-RANDGEN-DATA-HOUSEKEEPING.
MOVE FUNCTION CURRENT-DATE (9:8) TO SEED-TIME.
IF COUNT-OF-ACCESSES = ZERO
COMPUTE LOW-RANGE =
((SECONDS * HOURS * MINUTES * MS) / 3).
COMPUTE RANDOM-NUMBER-BUILT = RANDOM-NUMBER + LOW-RANGE.
COMPUTE HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE.
MOVE X2-POWER TO 2X2.
300-SET-2X2-DIVISOR.
IF 2X2 < (HIGH-RANGE + 1)
COMPUTE 2X2 = 2X2 * X2-POWER
GO TO 300-SET-2X2-DIVISOR.
* *********************************************************
* IF FIRST TIME THROUGH AND YOU WANT TO BUILD A SEED. *
* *********************************************************
IF COUNT-OF-ACCESSES = ZERO AND RANDOM-NUMBER = ZERO
COMPUTE RANDOM-NUMBER-BUILT =
((SECONDS * HOURS * MINUTES * MS) + HIGH-RANGE).
IF COUNT-OF-ACCESSES = ZERO
DISPLAY 'SEED TIME ' SEED-TIME
' RANDOM-NUMBER-BUILT ' RANDOM-NUMBER-BUILT
' LOW-RANGE ' LOW-RANGE.
* *********************************************
* END OF BUILDING A SEED IF YOU WANTED TO *
* *********************************************
* ***************************************************
* THIS PROCESS IS WHERE THE RANDOM-NUMBER IS BUILT *
* ***************************************************
400-RANDGEN-FORMULA.
COMPUTE FIRST-PART = (5 * RANDOM-NUMBER-BUILT) + 7.
DIVIDE FIRST-PART BY 2X2 GIVING WORKING-NUMBER
REMAINDER RANDOM-NUMBER-BUILT.
IF RANDOM-NUMBER-BUILT > LOW-RANGE AND
RANDOM-NUMBER-BUILT < (HIGH-RANGE + 1)
GO TO 600-RANDGEN-CLEANUP.
GO TO 400-RANDGEN-FORMULA.
* *********************************************
* GOOD RANDOM NUMBER HAS BEEN BUILT *
* *********************************************
600-RANDGEN-CLEANUP.
ADD 1 TO COUNT-OF-ACCESSES.
COMPUTE RANDOM-NUMBER =
RANDOM-NUMBER-BUILT - LOW-RANGE.
* *******************************************************
* THE NEXT 3 LINE OF CODE ARE FOR TESTING ON CONSOLE *
* *******************************************************
DISPLAY RANDOM-NUMBER.
IF COUNT-OF-ACCESSES < RANDOM-NUMBERS-NEEDED
GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.
900-EXIT-RANDGEN.
IF RANDOM-MSG NOT = SPACE
DISPLAY 'RANDOM-MSG: ' RANDOM-MSG.
MOVE ZERO TO COUNT-OF-ACCESSES RANDOM-NUMBERS-NEEDED RANDOM-NUMBER.
MOVE SPACE TO YOU-PROVIDE-SEED RUN-AGAIN.
DISPLAY 'RUN AGAIN Y OR N '
NO ADVANCING.
ACCEPT RUN-AGAIN.
IF (RUN-AGAIN = 'Y' OR 'y')
GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.
ACCEPT PAUSE-FOR-A-SECOND.
GOBACK.
Вы можете использовать хороший генератор псевдослучайных чисел с 10 битами и выбросить 1001–1023, оставив от 0 до 1000.
Отсюда мы получаем дизайн для 10-битного PRNG.
10 бит, полином обратной связи х ^10 + х ^7 + 1 (период 1023)
используйте Galois LFSR, чтобы получить быстрый код
Допустим, вы хотите просматривать перемешанные списки снова и снова, не имея O(n) задерживать каждый раз, когда вы начинаете заново, чтобы перемешать его снова, в этом случае мы можем сделать это:
Создайте 2 списка A и B, с 0 до 1000, занимает
2nпространство.Перемешать список А с использованием Фишера-Йейтса, принимает
nвремя.При рисовании числа сделайте 1-шаговый переход Фишера-Йейтса в другом списке.
Когда курсор находится в конце списка, переключитесь на другой список.
Preprocess
cursor = 0
selector = A
other = B
shuffle(A)
Рисовать
temp = selector[cursor]
swap(other[cursor], other[random])
if cursor == N
then swap(selector, other); cursor = 0
else cursor = cursor + 1
return temp
public static int[] randN(int n, int min, int max)
{
if (max <= min)
throw new ArgumentException("Max need to be greater than Min");
if (max - min < n)
throw new ArgumentException("Range needs to be longer than N");
var r = new Random();
HashSet<int> set = new HashSet<int>();
while (set.Count < n)
{
var i = r.Next(max - min) + min;
if (!set.Contains(i))
set.Add(i);
}
return set.ToArray();
}
N Неповторяющиеся случайные числа будут иметь сложность O(n), как требуется.
Примечание: Random должен быть статическим с применением безопасности потока.
Когда N больше 1000, и вам нужно нарисовать K случайных выборок, вы можете использовать набор, который пока содержит выборки. Для каждого розыгрыша вы используете выборку отбраковки, которая будет "почти" операцией O(1), поэтому общее время работы составляет почти O(K) при хранении O(N).
Этот алгоритм сталкивается с коллизиями, когда K "около" N. Это означает, что время работы будет намного хуже, чем O(K). Простое решение состоит в том, чтобы изменить логику так, чтобы при K > N/2 вы вели учет всех выборок, которые еще не были отрисованы. Каждый тираж удаляет образец из набора отклонений.
Другая очевидная проблема с выборкой отклонения состоит в том, что это O(N) хранилище, что является плохой новостью, если N исчисляется миллиардами или более. Тем не менее, есть алгоритм, который решает эту проблему. Этот алгоритм называется алгоритмом Виттера после его изобретателя. Алгоритм описан здесь. Суть алгоритма Виттера заключается в том, что после каждого розыгрыша вы вычисляете случайный пропуск, используя определенное распределение, которое гарантирует равномерную выборку.
Еще одна возможность:
Вы можете использовать массив флагов. И возьмите следующий, когда он уже выбран.
Но будьте осторожны после 1000 вызовов, функция никогда не закончится, поэтому вы должны принять меры предосторожности.
Большинство ответов здесь не гарантируют, что они не вернут одно и то же число дважды. Вот правильное решение:
int nrrand(void) {
static int s = 1;
static int start = -1;
do {
s = (s * 1103515245 + 12345) & 1023;
} while (s >= 1001);
if (start < 0) start = s;
else if (s == start) abort();
return s;
}
Я не уверен, что ограничение четко указано. Предполагается, что после 1000 других выходов значение может повторяться, но это наивно позволяет 0 следовать сразу после 0 до тех пор, пока они оба появляются в конце и в начале наборов 1000. Наоборот, пока можно сохранять расстояние 1000 других значений между повторениями, при этом возникает ситуация, когда последовательность воспроизводит себя одинаково каждый раз, потому что нет другого значения, которое произошло за пределами этого предела.
Вот метод, который всегда гарантирует не менее 500 других значений, прежде чем значение может быть повторено:
int nrrand(void) {
static int h[1001];
static int n = -1;
if (n < 0) {
int s = 1;
for (int i = 0; i < 1001; i++) {
do {
s = (s * 1103515245 + 12345) & 1023;
} while (s >= 1001);
/* If we used `i` rather than `s` then our early results would be poorly distributed. */
h[i] = s;
}
n = 0;
}
int i = rand(500);
if (i != 0) {
i = (n + i) % 1001;
int t = h[i];
h[i] = h[n];
h[n] = t;
}
i = h[n];
n = (n + 1) % 1001;
return i;
}
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
На самом деле это O(n-1), так как вам нужен только один своп для последних двух
Это C#
public static List<int> FisherYates(int n)
{
List<int> list = new List<int>(Enumerable.Range(0, n));
Random rand = new Random();
int swap;
int temp;
for (int i = n - 1; i > 0; i--)
{
swap = rand.Next(i + 1); //.net rand is not inclusive
if(swap != i) // it can stay in place - if you force a move it is not a uniform shuffle
{
temp = list[i];
list[i] = list[swap];
list[swap] = temp;
}
}
return list;
}
Пожалуйста, смотрите мой ответ на /questions/29450145/algoritm-otbora-prob-bez-zamenyi/29450154#29450154
Это один из простейших алгоритмов, имеющих среднюю сложность по времени O (s log s), обозначающую размер выборки. Там также есть несколько ссылок на алгоритмы хеш-таблиц, сложность которых, как утверждают, равна O (s).
Кто-то написал "создание случайных чисел в excel". Я использую этот идеал. Создайте структуру из 2 частей, str.index и str.ran; Для 10 случайных чисел создайте массив из 10 структур. Установите str.index от 0 до 9 и str.ran на другое случайное число.
for(i=0;i<10; ++i) {
arr[i].index = i;
arr[i].ran = rand();
}
Отсортируйте массив по значениям в arr[i].ran. Str.index теперь находится в случайном порядке. Ниже приведен код c:
#include <stdio.h>
#include <stdlib.h>
struct RanStr { int index; int ran;};
struct RanStr arr[10];
int sort_function(const void *a, const void *b);
int main(int argc, char *argv[])
{
int cnt, i;
//seed(125);
for(i=0;i<10; ++i)
{
arr[i].ran = rand();
arr[i].index = i;
printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
}
qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
printf("\n===================\n");
for(i=0;i<10; ++i)
{
printf("arr[%d] Random Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
}
return 0;
}
int sort_function(const void *a, const void *b)
{
struct RanStr *a1, *b1;
a1=(struct RanStr *) a;
b1=(struct RanStr *) b;
return( a1->ran - b1->ran );
}