ПерестаноBки

[experimenter]

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

Сообщение отредактировано: experimenter - 09.06.03, 20:50

[experimenter]

мужики, ну, давайте поднапряжемся и дадим мне ответ, а? плиз.

[Vesper]

Имхо это невозможно, без генерения... :'(

[experimenter]

Цитата vesper1, 10.06.03, 18:05:24

Имхо это невозможно, без генерения... :'(

ну, как так? я вот в книге одной читал и там как раз таки строилось такое соответсвие, только книгу эта сейчас для меня недоступна. :-/

[Demo_S]

я решения проблемы не знаю....
но мысли имеются:
найти некоторые инвариант перестанвки, ну или параметр перестановки, зависящий от номера. например кол-во инверсий.  на его основании выполнить все инверсии и поиметь перестановку.


кстати, почему не льзя заранее нагенерить, а потом по номеру из нагенеренного массива выдирать элемент. дешево и сердито:) (только места жрет)

[esperanto]

Ты знаешь я кажется полгода назад писал подробный ответ на это дело в этом разделе

ответ сейчас не вспомню но можешь поискать
если конечно я не путаю

[deil]

рассмотрим множество T(k) - произведение k множеств (с номерами от 1 до k), каждое из которых состоит из элементов от 0 до (k-i) (первое- 0,...,k-1, второе - 0,..,k-2, .., k-е - 0 )
очевидно, что мощность такого T(k) - k!
элемент, принадлежащий такому множеству представляется в виде (r1,  ...., rk)
в итоге T(k) - что-то вроде системы счисления с переменным основанием, т.е. для каждого (r1,  ...., rk) можно вычислить его номер (вроде так - n=r1*(k)+r2*(k)+..rk) и наоборот
пусть t1=(r1, .. , rk), t2=(R1, ... , Rk) -  наборы из T(k); t1 < t2, если до определённого i начала совпадают (r1=R1, .., r(i-1)=R(i-1)), а ri<Ri
перебор... будем перебирать всё это счастье в "естественном" порядке: увеличивая ri на 1, если переполнение - увеличиваем r(i-1) на единицу и т.д..

таким образом мы умеем для T(k) вычислять его мощность, вычислять номер элемента (от 1 до k!), по номеру - сам элемент, и делать перебор

а теперь - гвоздь программы:
пусть P(k) - множество всех перестановок чисел от 1 до k
отождествим T(k) и P(k):
P(k)->T(k): возьмём перестановку (r1, ..., rk) и сопоставим ей элемент (t1, ..., tk) так:
для любого i от 1 до k найдем число значений, меньших ri среди r(i+1), r(i+2), ..., rk - это число возьмём за ti
( пример: (4,8,1,5,7,2,3,6) -> (3,6,0,2,3,0,0,0) )
T(k)->P(k): меняя i от 1 до k, нужно просто помнить множество значений Si, которые ещё могут быть в перестановке на i-м месте
( пример: (3,6,0,2,3,0,0,0) -> (4,8,1,5,7,2,3,6) : S1=1:8; t1=3 => r1=4 (именно четвёрке в множестве S1 предшествует 3 числа); убираем 4 из S1: S2=1:3+5:8, t2=6 => r2=8 => S3=1:3+5+7+8 и т.д...)

в итоге, чтобы перебрать все P(k), или по номеру получить перестановку, нужно сначала аналогичное действие сделать для T(k), а потом сопоставить по указанному выше правилу нужную перестановку

удачи

[experimenter]

спасибо! и хоть некоторые части тут сразу не совсем очевидны, тем не менее.
и потом, а как быть-то если элементы повторяются?
и потом... по сложности алгоритма, я имею в виду время, не тоже самое будет, как если бы мы просто перебирали эти шутовы перестановки?

Сообщение отредактировано: experimenter - 15.06.03, 09:08

[deil]

ух
если что-нибудь останется загадкой - обращайся: у меня по этому всему экзамен в четверг :

"а как быть-то если элементы повторяются?" - в смысле?

[experimenter]

Цитата DEiL, 15.06.03, 13:07:56

ух
если что-нибудь останется загадкой - обращайся: у меня по этому всему экзамен в четверг :

"а как быть-то если элементы повторяются?" - в смысле?

насколько я понимаю, алгоритм работает для такого множества
(1,2,3,4) <- генерим все перестановки для этого мн-ва
а для такого работает?
(1,2,2,3) <- а для этого можем генерить?

Сообщение отредактировано: experimenter - 15.06.03, 09:11

[deil]

ой, я кажется понял, о чём ты :-)

ты о "abbccd"
ну так тут просто - отождестви каждую букву из искомой перестановки с числом каким-нибудь.. например с её позицией в строке.
и уже работай с набором чисел. они уже не будут повторяться
и когда у тебя будет получена перестановка, сделаешь обратное - цифру заменишь на букву
вроде бы так..

[deil]

читай выше :-)

[experimenter]

Цитата DEiL, 15.06.03, 13:11:46

ой, я кажется понял, о чём ты :-)

ты о "abbccd"
ну так тут просто - отождестви каждую букву из искомой перестановки с числом каким-нибудь.. например с её позицией в строке.
и уже работай с набором чисел. они уже не будут повторяться
и когда у тебя будет получена перестановка, сделаешь обратное - цифру заменишь на букву
вроде бы так..

а не получится, что у двух одинаковых перестановок будут разные представления?

[deil]

хм... да, ты прав - подстава..
блин

[experimenter]

все равно спасибо. 8D