Мне дали задание найти начальное число из серии псевдослучайно сгенерированных буквенно-цифровых идентификаторов, и после некоторого анализа я застрял в тупике, из которого, надеюсь, вы сможете меня вытащить .
Каждый идентификатор получается путем прохождения предыдущего через алгоритм шифрования, который я должен перепроектировать, чтобы найти начальное число. Список, данный мне, состоит из 2070 первых идентификаторов (без семени, очевидно). Идентификаторы начинаются с 4 буквенно-цифровых символов и через некоторое время меняются на 5 (например, "2xm1", "34nj", "avdfe", "2lgq9")
.Это переключение происходит, когда алгоритм после шифрования идентификатора возвращает идентификатор, который уже был сгенерирован ранее. В этот момент он добавляет один символ к этому возвращаемому идентификатору, делая его более длинным и, следовательно, уникальным. Затем он работает как обычно, генерируя идентификаторы новой длины. Фактически это означает, что алгоритм генерации является сюръективным.
Моей первой реакцией было попытаться преобразовать эти идентификаторы из base36 в какую-то другую базу, особенно десятичную. Я использовал результаты для точечной диаграммы диаграммы десятичных значений идентификаторов с точки зрения их ранга в списке, когда я заметил закономерность, происхождение которой не мог понять.
После выделения двух частей списка с точки зрения длины идентификатора я построил точечный график для подсписка четырехсимвольных идентификаторов и подсписка пятизначных идентификаторов, что позволило мне заметить странные узоры плотности.
После некоторого анализа я заметил две вещи:
- Для каждого подсписка разграничение между двумя плотностями составляет 6x36^(n-1), где n — количество символов в идентификаторе. Другими словами, это 1/6 всего диапазона значений для заданной длины идентификатора. Диапазон значений: [0; (36^n)-1]
- Перераспределение этих идентификаторов по отношению к этому пределу имеет тенденцию к 50/50, половина из них выше предела 1/6, половина из них ниже его.
Я пытался сопоставить такое поведение с другими известными диаграммами рассеяния ГПСЧ, но ни один из них не соответствовал тому, что я получаю на своих графиках.
Я надеюсь, что некоторые из вас могут знать о методе шифрования, формуле или функции, соответствующей такой конкретной диаграмме рассеяния, или иметь представление о том, что может происходить за кулисами.
Заранее спасибо за ответы.
Я не уверен, что правильно понял то, что вы описали. Должен ли я искать одинаковые точные закономерности распределения в обеих частях графиков? Я не совсем понимаю, что вы имеете в виду, когда говорите о «величине». Более того, я непреднамеренно оставил часть информации: мы обнаружили, что алгоритм добавляет 1 символ к длине сгенерированных идентификаторов, как только он встречает идентификатор, который уже был сгенерирован ранее. Это означает, что длина подсписков заранее не определена.
@PaulROBIN Я отредактировал ответ, чтобы попытаться упростить ситуацию.
О, это многое прояснило! Спасибо, я посмотрю на это! Единственное, что мне кажется странным, это то, что в случае части списка длиной в 4 символа идентификатор, предшествующий первому появлению дубликата, не совпадает с идентификатором, предшествующим второму появлению (первые 5 символов- длинный идентификатор). Это заставляет меня думать, что это может быть не последовательность, а только сюръективная функция.
Вот скриншоты отрывков, о которых я говорю