Является ли java.util.Random действительно так случайно? Как я могу сгенерировать 52! (факториал) возможные последовательности?

203

Я использовал, Random (java.util.Random)чтобы перетасовать колоду из 52 карт. Есть 52! (8.0658175e + 67) возможностей. Тем не менее, я обнаружил, что начальное число для java.util.Randoma long- намного меньше при 2 ^ 64 (1.8446744e + 19).

Отсюда я подозреваю, java.util.Random действительно ли это случайно ; действительно ли он способен генерировать все 52! возможности?

Если нет, то как я могу надежно генерировать лучшую случайную последовательность, которая может произвести все 52! возможности?

Серж Ардович
источник
21
«Как я могу сгенерировать реальное случайное число старше 52!» Числа от Randomникогда не являются реальными случайными числами. Это PRNG, где P означает «псевдо». Для реальных случайных чисел вам нужен источник случайности (например, random.org).
TJ Crowder
7
@JimGarrison Это не то, что после ОП. Он говорит о 10 ^ 68 возможных последовательностях. Поскольку каждая псевдослучайная последовательность идентифицируется своим начальным числом, OP говорит, что может быть не более 2 ^ 64 различных последовательностей.
dasblinkenlight
6
Я думаю, что это интересный вопрос, о котором стоит задуматься. Но я не могу не задаться вопросом о вашей проблемной ситуации: что именно приводит к требованию иметь возможность генерировать все 52! Перестановки? Например, в реальном бридже мы можем перетасовать колоду и сдавать по одной карте за раз, но есть только ~ 6e11 разных рук, поскольку много разных комбинаций приводят к одной и той же руке. Думая в другом направлении, нужно ли вам решение специально для 52 !, или вам нужно решение, которое обобщает, скажем, две колоды, перетасованные вместе (104! / (2 ** 52) возможностей, или ~ 2e150)?
NPE
9
@NPE - Возьмите пасьянс (Клондайк), например, 52! это точно количество возможных рук ..
Серж Ардович
3
Я думаю, что это интересное чтение: superuser.com/a/712583
Dennis_E

Ответы:

153

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

Плохая новость: нужно больше случайности.

Основным недостатком вашего подхода является то, что он пытается выбирать между ~ 226 вариантами, используя 64 бита энтропии (случайное начальное число). Чтобы честно выбрать между ~ 2 226 возможностями, вам нужно будет найти способ генерировать 226 битов энтропии вместо 64.

Существует несколько способов генерации случайных битов: выделенное оборудование , инструкции процессора , интерфейсы ОС , онлайн-сервисы . В вашем вопросе уже есть неявное предположение, что вы можете каким-то образом сгенерировать 64 бита, поэтому просто делайте то, что вы собирались сделать, только четыре раза, и жертвуйте лишние биты на благотворительность. :)

Хорошая новость: нужно меньше случайности.

Как только у вас есть эти 226 случайных битов, все остальное можно сделать детерминистически, и поэтому свойства java.util.Randomможно сделать неактуальными . Вот как.

Допустим, мы генерируем все 52! перестановки (потерпите меня) и сортируйте их лексикографически.

Чтобы выбрать одну из перестановок, нам нужно только одно случайное целое число между 0и 52!-1. Это целое число - наши 226 битов энтропии. Мы будем использовать его как индекс в нашем отсортированном списке перестановок. Если случайный индекс распределен равномерно, вы не только гарантируете, что все перестановки могут быть выбраны, они будут выбраны равновероятно (что является более сильной гарантией, чем вопрос).

Теперь вам не нужно генерировать все эти перестановки. Вы можете создать его напрямую, учитывая его случайно выбранную позицию в нашем гипотетическом отсортированном списке. Это можно сделать за время O (n 2 ) с использованием кода Лемера [1] (см. Также перестановки нумерации и факториальную систему счисления ). Здесь n - размер вашей колоды, т.е. 52.

Существует реализация C в этом ответе StackOverflow . Там есть несколько целочисленных переменных, которые переполняются при n = 52, но, к счастью, в Java вы можете использовать java.math.BigInteger. Остальные вычисления могут быть расшифрованы почти как есть:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

[1] Не путать с Лерером . :)

NPE
источник
7
Хех, и я был уверен, что ссылка в конце будет New Math . :-)
TJ Crowder
5
@TJCrowder: Это было почти! Это были бесконечно дифференцируемые римановы многообразия, которые качали его. :-)
NPE
2
Приятно видеть, что люди ценят классику. :-)
TJ Crowder
3
Где вы получаете случайные 226 бит в Java ? Извините, ваш код не отвечает.
Торстен С.
5
Я не понимаю, что вы имеете в виду, Java Random () также не обеспечит 64-битную энтропию. OP подразумевает неопределенный источник, который может выдавать 64 бита для заполнения PRNG. Имеет смысл предположить, что вы можете запросить один и тот же источник для 226 битов.
Прекратить причинять вред Монике
60

Ваш анализ верен: заполнение генератора псевдослучайных чисел любым конкретным начальным числом должно давать ту же последовательность после тасования, ограничивая число перестановок, которые вы можете получить, до 2 64 . Это утверждение легко проверить экспериментально , Collection.shuffleдважды позвонив , передав Randomобъект, инициализированный одним и тем же начальным числом, и заметив, что два случайных шаффла идентичны.

Решение этой проблемы состоит в том, чтобы использовать генератор случайных чисел, который учитывает большее начальное число. Java обеспечиваетSecureRandom класс, который можно инициализировать byte[]массивом практически неограниченного размера. Затем вы можете передать экземпляр SecureRandomto Collections.shuffleдля выполнения задачи:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);
dasblinkenlight
источник
8
Конечно, большое семя не является гарантией того, что все 52! Возможности будут созданы (о чем конкретно этот вопрос)? В качестве мысленного эксперимента рассмотрим патологический PRNG, который берет произвольно большое семя и генерирует бесконечно длинный ряд нулей. Кажется довольно ясным, что PRNG должен удовлетворять большему количеству требований, чем просто брать достаточно большое семя.
NPE
2
@SerjArdovic Да, любой начальный материал, передаваемый объекту SecureRandom, должен быть непредсказуемым, согласно документации Java.
dasblinkenlight
10
@NPE Вы правы, хотя слишком маленькое семя является гарантией верхнего предела, достаточно большое семя не гарантируется нижним пределом. Все, что это делает, - устранение теоретического верхнего предела, позволяющего ГСЧ генерировать все 52! комбинации.
dasblinkenlight
5
@SerjArdovic Наименьшее количество байтов, необходимое для этого, составляет 29 (вам нужно 226 бит для представления 52! Возможных битовых комбинаций, что составляет 28,25 байта, поэтому мы должны округлить его). Обратите внимание, что использование затравочного материала в 29 байт снимает теоретический верхний предел количества перемешиваний, которые вы можете получить, не устанавливая нижний предел (см. Комментарий NPE о дрянном ГСЧ, который берет очень большое семя и генерирует последовательность всех нулей).
dasblinkenlight
8
SecureRandomРеализация будет почти наверняка использовать основной ПСЧ. И от периода PRNG (и в меньшей степени от длины состояния) зависит, сможет ли он выбирать из 52 факторных перестановок. (Обратите внимание, что в документации говорится, что SecureRandomреализация «минимально соответствует» определенным статистическим тестам и генерирует выходные данные, которые «должны быть криптографически стойкими», но не устанавливает явного нижнего предела для длины состояния основного PRNG или его периода.)
Питер О.
26

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

java.util.Randomреализует алгоритм с модулем 2 48 ; таким образом, его длина состояния составляет всего 48 бит, что намного меньше, чем 226 бит, о которых я говорил. Вам нужно будет использовать другой PRNG с большей длиной состояния, в частности, с периодом 52 фактора или более.

Смотрите также «Перемешивание» в моей статье о генераторах случайных чисел .

Это соображение не зависит от характера PRNG; это в равной степени относится к криптографическим и некриптографическим PRNG (конечно, некриптографические PRNG неуместны, когда речь идет о защите информации).


Хотя java.security.SecureRandomпозволяет передавать семена неограниченной длины, SecureRandomреализация может использовать базовый PRNG (например, «SHA1PRNG» или «DRBG»). И от периода PRNG (и в меньшей степени от длины состояния) зависит, сможет ли он выбирать из 52 факторных перестановок. (Обратите внимание, что я определяю «длину состояния» как «максимальный размер затравки, которую PRNG может использовать для инициализации своего состояния без сокращения или сжатия этого затравки »).

Питер О.
источник
18

Позвольте мне заранее извиниться, потому что это немного сложно понять ...

Прежде всего, вы уже знаете, что java.util.Randomэто не совсем случайно. Он генерирует последовательности совершенно предсказуемым образом из семян. Вы совершенно правы, поскольку, поскольку начальное число имеет длину всего 64 бита, оно может генерировать только 2 ^ 64 различных последовательностей. Если бы вы как-то сгенерировали 64 реальных случайных бита и использовали их для выбора начального числа, вы не могли бы использовать этот начальный случайный выбор между всеми этими 52! возможные последовательности с равной вероятностью.

Однако этот факт не имеет никакого значения, если вы на самом деле не собираетесь генерировать более 2 ^ 64 последовательностей, если нет ничего «особенного» или «заметно особенного» в последовательностях 2 ^ 64, которые он может генерировать ,

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

Если вы не знаете, какой это был инициализатор, можете ли вы написать какой-либо тест, чтобы различить их? Если вам не повезло (в итоге) инициализировать плохой с одинаковыми 64 битами дважды, тогда ответ - нет. Вы не могли бы различить два инициализатора, не зная некоторых слабых мест в конкретной реализации PRNG.

В качестве альтернативы представьте, что Randomкласс имел массив из 2 ^ 64 последовательностей, которые были выбраны полностью и случайным образом в какое-то время в далеком прошлом, и что начальное число было просто индексом в этом массиве.

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

Конечно, для криптографических целей 64-разрядного начального числа просто недостаточно, поскольку получение системой, использующей одно и то же начальное число дважды, вычислительно возможно.

РЕДАКТИРОВАТЬ:

Я должен добавить, что, хотя все вышеперечисленное является правильным, фактическая реализация java.util.Randomне является удивительной. Если вы пишете карточную игру, возможно, используйте MessageDigestAPI для генерации хэша SHA-256 "MyGameName"+System.currentTimeMillis()и используйте эти биты для перетасовки колоды. По приведенному выше аргументу, пока ваши пользователи на самом деле не играют в азартные игры, вам не нужно беспокоиться о том, что currentTimeMillisвозвращает долго. Если ваши пользователи действительно играют в азартные игры, то используйте SecureRandomбез начальных затрат.

Мэтт Тиммерманс
источник
6
@ ThorstenS, как вы могли бы написать какой-либо тест, который мог бы определить, что есть комбинации карт, которые никогда не могут появиться?
Мэтт Тиммерманс
2
Существует несколько наборов тестов случайных чисел, таких как Diehard от George Marsaglia или TestU01 от Pierre L'Ecuyer / Richard Simard, которые легко находят статистические аномалии в случайных выходных данных. Для проверки карты вы можете использовать два квадрата. Вы определяете порядок карты. Первый квадрат показывает положение первых двух карт в виде пары xy: первая карта в виде x и разностное (!) Положение (-26-25) второй карты в качестве y. Второй квадрат показывает 3-ю и 4-ю карту с (-25-25) относительно 2-й / 3-й. Это сразу покажет пробелы и кластеры в вашем дистрибутиве, если вы запустите его на некоторое время.
Торстен С.
4
Ну, это не тот тест, который вы сказали написать, но он также не применим. Почему вы предполагаете, что в дистрибутиве есть пробелы и кластеры, которые могли бы обнаружить такие тесты? Это будет означать «особую слабость в реализации PRNG», как я уже упоминал, и не имеет никакого отношения к числу возможных семян. Такие тесты даже не требуют повторного заполнения генератора. В начале я предупредил, что это трудно понять.
Мэтт Тиммерманс
3
@ThorstenS. Эти тестовые наборы абсолютно не будут определять, является ли ваш источник 64-битным криптографически защищенным PRNG или истинным RNG. (В конце концов, тестирование PRNG - это то, для чего предназначены эти наборы.) Даже если вы знали, какой алгоритм используется, хороший PRNG делает невозможным определение состояния без поиска методом грубой силы в пространстве состояний.
Sneftel
1
@ThorstenS .: В реальной колоде карт подавляющее большинство комбинаций никогда не выпадет. Вы просто не знаете, что это такое. Для полуприличного PRNG это то же самое - если вы можете проверить, присутствует ли заданная выходная последовательность, которая длинна, в своем изображении, это недостаток в PRNG. Смешно огромное состояние / период как 52! не нужен; 128-бит должно быть достаточно.
R .. GitHub ОСТАНОВИТЬ ЛЬДА
10

Я собираюсь пойти по другому пути. Вы правы в своих предположениях - ваш PRNG не сможет ударить все 52! возможности.

Вопрос в том, каков масштаб вашей карточной игры?

Если вы делаете простую игру в стиле клондайка? Тогда вам определенно не нужны все 52! возможности. Вместо этого посмотрите на это так: у игрока будет 18 квинтиллионных игр. Даже учитывая «проблему дня рождения», им придется сыграть миллиарды рук, прежде чем они попадут в первую игру-дубликат.

Если вы делаете симуляцию Монте-Карло? Тогда ты, наверное, в порядке. Возможно, вам придется иметь дело с артефактами из-за 'P' в PRNG, но вы, вероятно, не столкнетесь с проблемами просто из-за малого начального пространства (опять же, вы смотрите на квинтиллионы уникальных возможностей). с другой стороны, если вы работаете с большим количеством итераций, тогда, да, ваше низкое начальное пространство может нарушить условия сделки.

Если вы делаете многопользовательскую карточную игру, особенно если на кону есть деньги? Затем вам нужно будет немного погуглить, как сайты онлайн-покера решают ту же проблему, о которой вы спрашиваете. Потому что, хотя проблема низкого начального пространства незаметна для среднего игрока, она пригодна для использования, если она того стоит. (Все покерные сайты прошли фазу, когда их PRNG были «взломаны», позволяя кому-то видеть закрытые карты всех других игроков, просто вынимая семя из открытых карт.) Если вы находитесь в такой ситуации, дона не просто найти лучший PRNG - вам нужно относиться к нему так же серьезно, как к проблеме криптографии.

Kevin
источник
9

Краткое решение, которое по сути то же самое, что и dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

Вам не нужно беспокоиться о внутреннем состоянии. Длинное объяснение почему:

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

Этот вход (!), Который все еще может содержать ложные следы, подается в криптографически сильный хеш, который удаляет эти следы. Вот почему эти CSPRNG используются, а не для создания самих номеров! Он SecureRandomимеет счетчик, который отслеживает, сколько битов было использовано ( getBytes()и getLong()т. Д.) И пополняет SecureRandomбиты энтропией, когда это необходимо .

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

Торстен С.
источник
4

Если вы рассматриваете число как просто массив битов (или байтов), то, возможно, вы могли бы использовать (Безопасные) Random.nextBytesрешения, предложенные в этом вопросе переполнения стека , и затем отобразить массив в new BigInteger(byte[]).

IvanK
источник
3

Очень простой алгоритм - применить SHA-256 к последовательности целых чисел, увеличивающейся от 0 и выше. (Соль может быть добавлена ​​при желании, чтобы «получить другую последовательность».) Если мы предположим, что вывод SHA-256 «так же хорош», как равномерно распределенные целые числа от 0 до 2 256 - 1, то у нас достаточно энтропии для задача.

Чтобы получить перестановку из вывода SHA256 (когда она выражается как целое число), нужно просто уменьшить ее по модулю 52, 51, 50 ... как в этом псевдокоде:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]
Artelius
источник