2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение08.10.2006, 23:18 
Аватара пользователя
О! Благодарю. Это мне вполне подходит.

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

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

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

 
 
 
 
Сообщение11.10.2006, 11:50 
Аватара пользователя
Понятно, что в первоначально предложенном отображении достаточно отображать каждую букву в перестановку 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$, ее номер - значение второй буквы и т.д.

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group