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

Question

Мне нужно создать программу / скрипт для создания большого количества случайных последовательностей (20 буквенных последовательностей на основе 4 разных букв) с минимальным расстоянием редактирования между всеми последовательностями. "Высокий" - это минимум 100 тыс. Последовательностей, но, если возможно, до 1 млн.

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

Как вы понимаете, это очень плохо масштабируется для большего количества последовательностей. До 10 тыс. Это вполне нормально, но при попытке получить 100 тыс. Это становится проблематичным.

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

Я пытался придумать альтернативы для ускорения процесса, например, построение последовательностей - это "блоки" минимального ED, а затем объединение, но они не нашли никакого решения.

Хотите знать, есть ли у кого-нибудь умная идея / метод, который мог бы быть реализован для создания такого большого количества последовательностей с минимальным ED и более эффективным по времени?

Ура, JB

Answer 1

Из википедии кажется, что расстояние редактирования - это одна из трех операций: вставка, удаление, замена; выполняется на начальной строке. Почему бы систематически не генерировать все строки до N правок из начальной строки, а затем останавливаться, когда вы достигнете своего предела?

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