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

Question

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

1. это должна быть уникальная строка;
2. длина строки должна быть 8 символов;
3. itдолжен содержать 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 заглавных букв от A до Z
• , которые вы хотели бы равномерно распределить случайную строку

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

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

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

---

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

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

1. Повторите следующий шаг 6 раз:
2. Возьмите X mod 26, сгенерируйте заглавную букву и установите X = X / 26.
3. Возьмите X mod 100, чтобы сгенерировать две цифры, и установите X = X / 100.
4. X теперь будет от 0 до 17 включительно (2 ³⁹ / 26 ⁶ / 100 = 17,796 ...).Сопоставьте это число с двумя позициями уникальных цифр (вероятно, проще всего с помощью таблицы поиска, поскольку мы говорим только о 28 возможностях. Если у вас было больше, используйте алгоритм Флойда для генерации уникальной перестановки и используйте переменную-базовый метод mod + целочисленное деление вместо генерации случайного числа).
5. Следуйте приведенному выше случайному подходу, но вместо этого используйте числа, сгенерированные этим алгоритмом.-битные числа, и если выход вашей сети Feistel> N _comb , то увеличьте счетчик и попробуйте снова.Это покрывает все строковое пространство за счет отклонения недопустимых чисел и необходимости повторного выполнения алгоритма.(Но вам не нужна база данных, чтобы сделать это.)

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

Answer 2

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

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

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

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

Answer 3

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

Самое простое решение - пересчитать ваши коды .

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

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

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

Answer 4

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

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

и т. Д.

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Answer 7

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

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

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

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