Алгоритм генерации подстановок

[Woland]

Есть множество M всех слов, состоящих из 30 букв каждое. Каждая буква может принимать
одно из 64 различных значений. Требуется построить биекцию данного множества
на подмножество S_{256}. Алгоритм устанавливающий такую биекцию,
должен работать быстро, а не в принципе решать данную задачу.

[maxal]

Достаточно первую букву отобразить в перестановку элементов 1..8, вторую - в перестановку элементов 9..16, и т.д., 30-ю - в перестановку элементов 233..240, а затем конкатенировать эти перестановки.
При этом отображение буквы в перестановку 8-ми элементов можно задать таблично.

[Woland]

О! Благодарю. Это мне вполне подходит.

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

[maxal]

Woland писал(а):

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

Читайте А.Шень "Программирование: теоремы и задачи"

[maxal]

Понятно, что в первоначально предложенном отображении достаточно отображать каждую букву в перестановку 5 элементов (так как $5!\geq 64$), в результате такой способ даст перестановку длины не меньше $30\cdot 5=150$.
А вот довольно простая конструкция отображения слов в $S_{93}$.

Начнем с "пустой" перестановки, если $i$-я буква ($i=1,\dots,30$) в слове равна $k$ ($1\leq k\leq 64$), то ставим число $i$ на $k$-е пустое место в перестановке. Элементы $31,\dots,93$ расставляем на оставшиеся пустые места в произвольном порядке.

Обратно получить слово по заданной перестановке тоже легко: смотрим на какой позиции в перестановке стоит $1$: номер позиции - это значение первой буквы; удаляем элемент $1$ из перестановки и смотрим на какой позиции стоит $2$, ее номер - значение второй буквы и т.д.

[Woland]

Есть ещё одна проблема: необходимо биекцию организовать так, что бы
"близким" прообразам ставились в соответствие "далёкие" -образы.
Т.е. например:
aa...a ------>(1,2,3,4,...,255)
aa..ab ------>(67,89,32,189,....,10,1)
здесь исходные элементы отличаются не значительно(всего одной буквой на конце) , зато
образы отличаются значительно.
Интересен прежде всего как сформулировать сам критерий "близости".