Алгоритм для распечатывания переставленного списка, оперативного и с O (1) память

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

Существуют математические способы получения «случайные» перестановки N целых чисел, поэтому, если P является такой перестановкой от 0..N-1 до 0..N-1, вы можете просто перебрать x от 0 до N-1 и вывести элемент списка L (P (x)) вместо L (x), и вы получили перетасовку. Такие перестановки могут быть получены, например, с использованием модульной арифметики. Например, если N простое число, P (x) = (x * k) mod N является перестановкой для любого 0

Следует отметить, что модульное возведение в степень является основой для многих криптографических алгоритмов (например, RSA, Diffie-Hellman) и специалистами в этой области считается сильно псевдослучайной операцией. .

Другой простой способ (не требующий простых чисел) - сначала расширить область определения так, чтобы вместо N вы рассматривали M, где M - наименьшая степень двойки над N. Так, например, если N = 12, вы устанавливаете M = 16. Затем вы используете биективные битовые операции, например

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf

Затем, когда вы выводите свой список, вы выполняете итерацию x от 0 до M-1 и выводите L (P (x)), только если P (x) фактически

«Истинное, несмещенное случайное» решение может быть построено путем исправления криптостойкого блочного шифра (например, AES) и случайный ключ (k), а затем повторение последовательности

AES(k, 0), AES(k, 1), ...

и вывод соответствующего элемента из последовательности, если и только если AES (k, i)

Вам не разрешено делать копию, изменять ее или отслеживать, какие элементы вы посетили? Я скажу, что это невозможно. Если я не понимаю ваш третий критерий.

Я так понимаю, что вам не разрешено говорить: создайте массив из 10 000 000 соответствующих логических значений, для которых установлено значение true, когда вы напечатали соответствующий элемент. И вам не разрешается составлять список из 10 000 000 индексов, перемешивать список и распечатывать элементы в таком порядке.

Эти 10 000 000 элементов являются лишь ссылками (или указателями) на фактические элементы, поэтому ваш список не будет таким большим. Только ~ 40 МБ на 32-битной архитектуре для всех ссылок + размер внутренних переменных этого списка. В случае, если ваши позиции меньше эталонного размера, вы просто копируете весь список.

It's not possible to do this with a truly random number generator since you either have to:

• remember which numbers have already been chosen and skip them (which requires an O(n) list of booleans and progressively worsening run-times as you skip more and more numbers); or
• reduce the pool after each selection (which requires either modifications to the original list or a separate O(n) list to modify).

Neither of those are possibilities in your question so I'm going to have to say "no, you can't do it".

What I would tend to go for in this case is a bit mask of used values but not with skipping since, as mentioned, the run-times get worse as the used values accumulate.

A bit mask will be substantially better than the original list of 39Gb (10 million bits is only about 1.2M), many order of magnitude less as you requested even though it's still O(n).

In order to get around the run-time problem, only generate one random number each time and, if the relevant "used" bit is already set, scan forward through the bit mask until you find one that's not set.

That means you won't be hanging around, desperate for the random number generator to give you a number that hasn't been used yet. The run times will only ever get as bad as the time taken to scan 1.2M of data.

Of course this means that the specific number chosen at any time is skewed based on the numbers that have already been chosen but, since those numbers were random anyway, the skewing is random (and if the numbers weren't truly random to begin with, then the skewing won't matter).

And you could even alternate the search direction (scanning up or down) if you want a bit more variety.

Bottom line: I don't believe what you're asking for is doable but keep in mind I've been wrong before as my wife will attest to, quickly and frequently :-) But, as with all things, there's usually ways to get around such issues.

Звучит невозможно.

Но 10 000 000 64-битных указателей занимают всего около 76 МБ.

Сдвиговый регистр с линейной обратной связью может делать практически все, что вы хотите - генерировать список чисел до некоторого предела, но в (разумном) случайном порядке. Образцы, которые он производит, статистически схожи с тем, что вы ожидаете от случайной попытки, , но это даже близко не к криптографической безопасности. Алгоритм Берлекампа-Месси позволяет вам реконструировать эквивалентный LFSR на основе выходной последовательности.

Учитывая ваши требования к списку из ~ 10 000 000 элементов, вам нужен 24-битный LFSR максимальной длины и просто отбрасывать выходные данные. больше, чем размер вашего списка.

Как бы то ни было, LFSR обычно довольно быстр по сравнению с типичным линейным конгруэнтным PRNG того же периода. Аппаратно LFSR чрезвычайно прост, он состоит из N-битного регистра,

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

Если места недостаточно, вы можете сделать то же самое, не сохраняя узлы указатели, но время будет страдать (это компромисс между пространством и временем ☺).

Вы можете создать псевдослучайную «безопасную» перестановку, используя блочный шифр - см. здесь . Ключевой вывод заключается в том, что, учитывая блочный шифр длиной n бит, вы можете использовать «сворачивание», чтобы сократить его до m

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

Вот наполовину готовая идея: вы могли бы неплохо справиться, выбирая простое число p немного больше n, затем выбирается случайный x между 1 и p-1, порядок которого в мультипликативной группе mod p равен p-1 (выберите случайные xs и проверьте, какие из них удовлетворяют x ^ i! = 1 для i

= n, и это даст вам последовательность индексов для печати. ​​

Это не совсем случайно, но вы можете использовать одну и ту же технику несколько раз, взяв указанные выше индексы (+1) и используя их как показатели другого генератора x2 по модулю другого простого числа p2 (вам понадобится n