Создание неповторяющихся случайных чисел в Python

Хорошо, это один из тех сложнее, чем звучит вопрос, поэтому я перехожу к переполнению стека, потому что не могу придумать хороший ответ. Вот что я хочу: мне нужен Python для создания простого списка чисел от 0 до 1 000 000 000 в случайном порядке, который будет использоваться для серийных номеров (используя случайное число, чтобы вы не могли определить, сколько из них было назначено или время атаки так же легко, т.е. угадать следующий, который появится). Эти номера хранятся в таблице базы данных (индексируются) вместе с информацией, связанной с ними. Программа, генерирующая их, не работает вечно, поэтому не может полагаться на внутреннее состояние.

Не так ли? Просто сгенерируйте список чисел, вставьте их в массив и используйте Python "random.shuffle(big_number_array)", и мы закончили. Проблема в том, что я бы хотел избежать хранения списка чисел (и, таким образом, прочитать файл, поместить его сверху, сохранить файл и закрыть его). Я бы лучше их сработал на лету. Проблема в том, что решения, о которых я могу думать, имеют проблемы:

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

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

3) Создайте случайное число, а затем проверьте, использовалось ли оно. Если он был использован, добавьте или вычтите другое случайно генерируемое случайное число и снова проверьте, проблема в том, что мы вернулись к простому генерированию случайных чисел и проверке, как в решении 1.

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

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

6) Подготовьте или добавьте информацию о времени на случайное число (например, временную метку unix), чтобы уменьшить вероятность столкновения, опять же я получаю больше чисел, чем мне нужно.

У кого-нибудь есть умные идеи, которые уменьшат шансы "столкновения" (т.е. генерируют случайное число, которое уже принято), но также позволят мне сохранить число "маленькое" (т.е. менее миллиарда (или тысяча миллионов для ваших европейцев =)).

Ответ и почему я его принял:

Итак, я просто пойду с 1 и надеюсь, что это не проблема, однако, если это так, я пойду с детерминированным решением для генерации всех чисел и хранения их, чтобы существовало произвольное получение нового случайного числа, и я могу использовать "маленькие" цифры (т.е. 9 цифр вместо MD5/и т.д.).

Ответ 1

Это аккуратная проблема, и я думал об этом некоторое время (с решениями, подобными Sjoerd's), но, в конце концов, вот что я думаю:

Используйте свою точку 1) и перестаньте беспокоиться.

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

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

Даже если вы близки к тому, что ранее выбрали миллиард чисел, вероятность того, что ваш новый номер уже занят, остается только 0,1%.

Сделайте шаг 1 и снова нарисуйте. Вы все еще можете проверить "бесконечный" цикл, скажем, не пытайтесь больше 1000 раз или около того, а затем отбрасывать на добавление 1 (или что-то еще).

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

Ответ 2

Вы можете использовать Format-Preserving Encryption для шифрования счетчика. Ваш счетчик просто идет от 0 вверх, и шифрование использует ключ по вашему выбору, чтобы превратить его в кажущееся случайным значение любого необходимого радиуса и ширины.

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

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

AES-FFX - один из предлагаемых стандартных методов для достижения этого.

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

0000000   0731134
0000001   6161064
0000002   8899846
0000003   9575678
0000004   3030773
0000005   2748859
0000006   5127539
0000007   1372978
0000008   3830458
0000009   7628602
0000010   6643859
0000011   2563651
0000012   9522955
0000013   9286113
0000014   5543492
0000015   3230955
...       ...

Для другого примера в Python, используя другой метод, отличный от AES-FFX (я думаю), см. это сообщение в блоге "Как создать номер учетной записи" , который делает FPE с использованием шифрования Feistel. Он генерирует числа от 0 до 2 ^ 32-1.

Ответ 3

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

modulo = 87178291199 # prime
incrementor = 17180131327 # relative prime

current = 433494437 # some start value
for i in xrange(1, 100):
    print current
    current = (current + incrementor) % modulo

Ответ 4

Если они не должны быть случайными, но просто не явно линейными (1, 2, 3, 4,...), то здесь простой алгоритм:

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

max_value = 795028841
step = 360287471
previous_serial = 0
for i in xrange(0, max_value):
    previous_serial += step
    previous_serial %= max_value
    print "Serial: %09i" % previous_serial

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

s = set()
with open("test.txt", "w+") as f:
    previous_serial = 0
    for i in xrange(0, 2711):
        previous_serial += 1811
        previous_serial %= 2711
        assert previous_serial not in s
        s.add(previous_serial)

Вы также можете доказать это эмпирически с 9-значными штрихами, это просто займет немного больше работы (или намного больше памяти).

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

Ответ 5

Если вам не нужно что-то криптографически безопасное, а просто "достаточно запутано"...

Поля Галуа

Вы можете попробовать выполнить операции в Galois Fields, например. GF (2) ³² чтобы сопоставить простой приращающийся счетчик x с кажущимся случайным порядковым номером y:

x = counter_value
y = some_galois_function(x)

Умножение на константу
- Инверсия должна умножаться на обратную константу
Поднимитесь на мощность: x ⁿ
Взаимный x ^-1
- Специальный случай повышения мощности n
- Это его собственный обратный
Exponentiation примитивного элемента: a ^x
- Обратите внимание, что это не имеет легко вычисленного обратного (дискретного логарифма)
- Убедитесь, что a является примитивным элементом, aka generator

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

Как найти библиотеку для поля Галуа для Python... хороший вопрос. Если вам не нужна скорость (что бы вы не сделали для этого), вы могли бы сделать свой собственный. Я не пробовал:

NZMATH
Пакет Python с конечным полем
Sage, хотя это целая среда для математических вычислений, гораздо больше, чем просто библиотека Python

Матричное умножение в GF (2)

Выберите подходящую 32 × 32 обратимую матрицу в GF (2) и умножите на нее 32-разрядный входной счетчик. Это концептуально связано с LFSR, как описано в ответе S.Lott.

CRC

Связанная возможность заключается в использовании вычисления CRC. На основании остатка длинного деления с неприводимым многочленом в GF (2). Код Python легко доступен для CRC (crcmod, pycrc), хотя вам может понадобиться выбрать другой неприводимый многочлен, чем обычно используется для ваших целей. Я немного расплывчатый в теории, но я думаю, что 32-битный CRC должен генерировать уникальное значение для каждой возможной комбинации 4-байтовых входов. Проверь это. Достаточно просто экспериментально проверить это, подав выход обратно на вход и проверив, что он производит полный цикл длины 2 ³² -1 (нуль только сопоставляет нулю). Возможно, вам придется избавиться от любых исходных/окончательных XOR в алгоритме CRC, чтобы эта проверка работала.

Ответ 6

Я думаю, что вы переоцениваете проблемы с подходом 1). Если у вас нет жестких требований в реальном времени, проверка только случайным выбором заканчивается довольно быстро. Вероятность того, что требуется больше, чем несколько итераций, экспоненциально убывает. При выпуске 100M (10% fillfactor) у вас будет один шанс на миллиард, требующий более 9 итераций. Даже при 50% принятых чисел вам потребуется в среднем 2 итерации и один из миллиардов шансов потребовать более 30 проверок. Или даже крайний случай, когда 99% числа уже приняты, может быть разумным - вы усредняете 100 итераций и имеете 1 в миллиард изменение требующих 2062 итераций

Ответ 7

Стандартная последовательность семян генератора случайных чисел Linear Congruential НЕ МОЖЕТ повторять до тех пор, пока не будет сгенерирован полный набор чисел из начального начального значения. Затем он ДОЛЖЕН повториться точно.

Внутреннее семя часто бывает большим (48 или 64 бит). Сгенерированные числа меньше (обычно 32 бита), потому что весь набор бит не является случайным. Если вы будете следовать за значениями семян, они образуют четкую неповторяющуюся последовательность.

Вопрос состоит, по существу, в том, чтобы найти хорошее семя, которое генерирует "достаточные" числа. Вы можете выбрать семя и генерировать числа, пока не вернетесь к исходному семени. Это длина последовательности. Это могут быть миллионы или миллиарды чисел.

В Кнуте есть некоторые рекомендации по выбору подходящих семян, которые будут генерировать очень длинные последовательности уникальных чисел.

Ответ 8

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

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

Совершенно очевидно, что после сбора 10 чисел ваш пул возможных случайных чисел будет уменьшен на 10. Поэтому вы не должны выбирать число от 1 до 1.000.000, но между 1 и 999.990. Конечно, это число не является действительным числом, а только индексом (если только 10 номеров не были 999.991, 999.992,...); youd должны рассчитывать теперь от 1, опуская все уже собранные числа.

Конечно, ваш алгоритм должен быть более умным, чем просто счет от 1 до 1.000.000, но я надеюсь, что вы поймете метод.

Мне не нравится рисовать случайные числа, пока я не получу тот, который подходит. Это просто неправильно.

Ответ 9

Мое решение https://github.com/glushchenko/python-unique-id, я думаю, вы должны расширить матрицу для 1,000,000,000 вариаций и повеселиться.

Ответ 10

Я бы переосмыслил проблему самостоятельно... Кажется, вы не делаете ничего последовательного с цифрами... и у вас есть индекс в столбце, в котором они есть. Действительно ли они нужны для чисел?

Рассмотрим ша-хэш... вам действительно не нужно все. Сделайте то, что git или другие услуги сокращения URL-адресов, и возьмите первые 3/4/5 символа хэша. Учитывая, что у каждого персонажа теперь есть 36 возможных значений вместо 10, у вас есть 2 176 782 336 комбинаций вместо 999 999 комбинаций (для шести цифр). Объедините это с быстрой проверкой того, существует ли комбинация (чистый индексный запрос) и семя, как временная метка + случайное число, и это должно выполняться практически для любой ситуации.

Ответ 11

Вам нужно, чтобы это было криптографически безопасным или просто сложно догадаться? Насколько плохи столкновения? Потому что, если это должно быть криптографически сильным и иметь нулевые столкновения, это, к сожалению, невозможно.

Ответ 12

Я начал писать объяснение подхода, используемого ниже, но просто реализовать его было проще и точнее. Этот подход имеет странное поведение, которое ускоряет тем больше чисел, которые вы создали. Но он работает, и он не требует, чтобы вы генерировали все цифры заранее.

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

import random

class NonRepeatingRandom(object):

    def __init__(self, maxvalue):
        self.maxvalue = maxvalue
        self.used = set()

    def next(self):
        if len(self.used) >= self.maxvalue:
            raise StopIteration
        r = random.randrange(0, self.maxvalue - len(self.used))
        result = 0
        for i in range(1, r+1):
            result += 1
            while result in self.used:
                 result += 1
        self.used.add(result)
        return result

    def __iter__(self):
        return self

    def __getitem__(self):
        raise NotImplemented

    def get_all(self):
        return [i for i in self]

>>> n = NonRepeatingRandom(20)
>>> n.get_all()
[12, 14, 13, 2, 20, 4, 15, 16, 19, 1, 8, 6, 7, 9, 5, 11, 10, 3, 18, 17]

Ответ 13

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

Если вы думаете, что может быть кто-то, у кого будет серьезный интерес угадать следующие значения, вы можете использовать последовательность базы данных для подсчета генерируемых вами значений и шифрования их с помощью алгоритма шифрования или другого криптографически сильного совершенства. Однако вам нужно позаботиться о том, чтобы алгоритм шифрования не был легко разбит, если можно получить последовательность последовательных чисел, которые вы создали - простой RSA, например, не сделает этого из-за Franklin-Reiter Related Message Attack.

Ответ 14

Бит позднего ответа, но я нигде не видел этого.

Почему бы не использовать модуль uuid, чтобы создать глобально уникальные идентификаторы

Ответ 15

Чтобы создать список полностью случайных чисел в пределах определенного порога, выполните следующие действия:

plist=list()
length_of_list=100
upbound=1000
lowbound=0
while len(pList)<(length_of_list):
     pList.append(rnd.randint(lowbound,upbound))
     pList=list(set(pList))

Ответ 16

Я столкнулся с той же проблемой и открыл вопрос с другим заголовком, прежде чем перейти к этому. Мое решение - это генератор случайных выборок индексов (т.е. неповторяющихся чисел) в интервале [0,maximal), называемый itersample. Вот несколько примеров использования:

import random
generator=itersample(maximal)
another_number=generator.next() # pick the next non-repeating random number

или

import random
generator=itersample(maximal)
for random_number in generator:
    # do something with random_number
    if some_condition: # exit loop when needed
        break

itersample генерирует не повторяющиеся случайные целые числа, потребность в хранении ограничена выбранными числами, а время, необходимое для выбора чисел n, должно быть (как подтверждают некоторые тесты) O(n log(n)), относится к maximal.

Вот код itersample:

import random
def itersample(c): # c = upper bound of generated integers
    sampled=[]
    def fsb(a,b): # free spaces before middle of interval a,b
        fsb.idx=a+(b+1-a)/2
        fsb.last=sampled[fsb.idx]-fsb.idx if len(sampled)>0 else 0
        return fsb.last
    while len(sampled)<c:
        sample_index=random.randrange(c-len(sampled))
        a,b=0,len(sampled)-1
        if fsb(a,a)>sample_index:
            yielding=sample_index
            sampled.insert(0,yielding)
            yield yielding
        elif fsb(b,b)<sample_index+1:
            yielding=len(sampled)+sample_index
            sampled.insert(len(sampled),yielding)
            yield yielding
        else: # sample_index falls inside sampled list
            while a+1<b:
                if fsb(a,b)<sample_index+1:
                    a=fsb.idx
                else:
                    b=fsb.idx
            yielding=a+1+sample_index
            sampled.insert(a+1,yielding)
            yield yielding

Ответ 17

Вы заявляете, что сохраняете числа в базе данных.

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

Примеры

MySQL:

SELECT column FROM table
ORDER BY RAND()
LIMIT 1

PostgreSQL:

SELECT column FROM table
ORDER BY RANDOM()
LIMIT 1