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

Ответ 1

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

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

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

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

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

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

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

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

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

В этом fooobar.com/questions/159163/... есть реализация C. Там есть несколько целых переменных, которые переполняли бы для 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] Не путать с Лерером. :)

Ответ 2

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

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

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

Ответ 3

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

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

Короткое решение, которое, по сути, одинаково для dasblinkenlight:

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

Collections.shuffle(deck, random);

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

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

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

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

Ответ 7

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

Ответ 8

Очень простой алгоритм - применить 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]