Алгоритмы: случайные уникальная строка

Question

Мне нужно создать строку, которая отвечает следующим требованиям:

1. она должна быть уникальная строка;
2. длина строки должна быть 8 символов;
3. он должен содержать 2 цифры;
4. все символы (нецифровые символы) должны быть в верхнем регистре.

Я буду хранить их в базе данных после генерации (они будут назначены другим объектам).

Мое намерение состоит в том, чтобы сделать что-то вроде этого:

1. Сформировать 2 случайные значения от 0 до 9 — они будут использоваться для цифр в строке;
2. сгенерируйте 6 случайных значений от 0 до 25 и добавьте их в 64 —, они будут использоваться в качестве 6 символов;
3. объединить все в одну строку;
4. проверить, существует ли строка в базе данных; если не — повтор.

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

Вопрос: не могли бы вы дать советы о том, как улучшить этот алгоритм, чтобы быть более детерминированным?

Спасибо.

Answer 1

1. это должна быть уникальная строка;
2. длина строки должна быть 8 символов;
3. должно содержать 2 цифры;
4. все символы (нецифровые символы) - должны быть в верхнем регистре.

Предполагая:

• требования # 2 и # 3 точно (ровно 8 символов, ровно 2 цифры), а не минимум
• в "символы", в требовании # 4 являются 26 заглавные буквы от А до Z
• вы хотели бы равномерно распределенную случайную строку

Тогда ваш предлагать d имеет два вопроса. Во-первых, буквы A - Z являются ASCII 65 - 90, а не 64 - 89. Другим является то, что он не равномерно распределяет числа в пределах возможного пространства строк. Это можно исправить следующим образом:

1. Создайте два разных целых числа от 0 до 7 и отсортируйте их.
2. Сформировать 2 случайных чисел от 0 до 9.
3. Сформировать 6 случайных букв от А до Я.
4. Используйте два различных числа в шаге 1 в позиции, и поставить 2 номера в этих позициях.
5. Поместите 6 случайных букв в оставшиеся позиции.

Есть 28 возможностей для двух различных целых чисел ((8 * 8 - 8 дублирует)/2 Упорядочения), 26 возможности для писем и 100 возможности для чисел, общее кол-во в силе комбинации: N _{гребенка} = 864964172800 = 8,64 x 10 .

---

редактировать: Если вы хотите, чтобы избежать баз данных для хранения, но по-прежнему гарантировать как уникальность строк и у них криптографический безопасные, лучше всего это криптографический случайная биекция из счетчика между 0 и N _max < = N _{гребенка} подмножество пространства возможных выходных строк. (Bijection означает, что между выходной строкой и входным счетчиком существует взаимно однозначное соответствие.)

Это возможно с помощью Feistel networks, которые обычно используются в хэш-функциях и симметричной криптографии (включая AES). Вы, вероятно, хотите, чтобы выбрать N _макс = 2 что наибольшая степень 2 < = N _{гребнем} и использовать 39-битную Фейстеля сети с использованием постоянного ключа вы держите в секрете. Затем вы подключите счетчик к сети Фейстеля, и прибывает еще 39-разрядное число X, который затем преобразовать в соответствующую строку следующим образом:

1. Повторите следующий шаг 6 раз:
2. Take X mod 26, сгенерируйте заглавную букву и установите X = X/26.
3. Возьмите X mod 100, чтобы сгенерировать две цифры, и установите X = X/100.
4. X теперь будет между 0 и 17 включительно (2 /26 /100 = 17.796 ...). Сопоставьте это число с двумя уникальными позициями цифр (возможно, проще всего использовать таблицу поиска, поскольку мы говорим только о 28 вариантах. Если у вас было больше, используйте Floyd's algorithm for generating a unique permutation и используйте технику с переменной базой mod + integer divide вместо генерации случайного номер).
5. Следуйте случайному подходу выше, но вместо этого используйте числа, сгенерированные этим алгоритмом.

В качестве альтернативы, использовать 40-разрядные числа, и если выход из вашей сети криптографической является> N _{гребень}, то увеличивает счетчик и повторите попытку. Это охватывает все пространство строки за счет отказа от недопустимых чисел и необходимости повторного выполнения алгоритма. (Но для этого вам не нужна база данных.)

Но это не то, что нужно, если вы не знаете, что делаете.

Answer 2

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

for letters in ('AAAAAA' .. 'ZZZZZZ') { 
    for numbers in (00 .. 99) { 
    string = letters + numbers 
    } 
} 

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

Если вам нужны произвольно сгенерированные строки, то вам нужно сохранить какую-то запись, какие строки были ранее сгенерированы, поэтому вам придется ударить по БД (или сохранить их все в памяти или написать их в текстовый файл) и проверьте этот список.

Answer 3

Я думаю, что вы хорошо входите в свои десятки тысяч таких идентификаторов, и даже после этого вы, скорее всего, в порядке.

Теперь, если вы хотите какой-то детерминизм, вы всегда можете заставить пароль после определенного количества сбоев. Скажем, после 50 неудач, вы произвольно выбираете пароль и увеличиваете его часть на 1, пока не получите бесплатный.

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

Answer 4

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

Если «случайный» является требованием, вы можете сделать несколько улучшений.

1. Сохраните строку как номер в базе данных. Не уверен, насколько это улучшает перфоманс.
2. Не храните используемые строки вообще. Вы можете использовать «индексный» подход выше, но преобразовать целочисленное число в строку, казалось бы, случайным образом (например, используя сдвиг бит). Без особых исследований никто не увидит узор.

Например, если у нас есть последовательность 1, 2, 3, 4, ... и используйте циклический двоичный сдвиг вправо на 1 бит, он будет превращен в 4, 1, 5, 2, ... (предполагается, что у нас есть только 3 бита) Это тоже не должно быть сдвигом, это может быть перестановка или любая другая «рандомизация».

Answer 5

Эти пароли пользователей? Если это так, необходимо учитывать несколько вещей:

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

Что касается 2, вы можете избежать проблемы, используя LLNLLNLL в качестве шаблона (L = буква, N = номер).

Если вам нужно 1 миллион паролей из пула в 2,5 миллиарда долларов, вы обязательно столкнетесь с конфликтами в своей базе данных, поэтому вам придется иметь дело с ними изящно. Но простого повторения достаточно, если ваш генератор случайных чисел прочен.

Answer 6

Сделай наоборот: генерировать один большой случайное число, которое вы расколоть до получения отдельных символов:

long bigrandom = ...; 
int firstDigit = bigRandom % 10; 
int secondDigit = (bigrandom/10) % 10; 

и так далее.

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

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

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

Answer 7

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

Простейшим решением является предварительный расчет ваших кодов.

Начните с первого кода 00AAAA и прирастайте для создания 00AAAB, 00AAAC ... 99ZZZZ. Вставьте их в таблицу в случайном порядке. Когда вам нужен новый код, извлеките в верхнюю запись неиспользуемую запись из таблицы (затем отметьте ее как использованную). Это не огромный стол, как указано выше - всего несколько миллионов записей.

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

Если вам когда-нибудь понадобится больше «кодов», просто сгенерируйте несколько «случайных» строк и добавьте их в таблицу.