Ищется алгоритм перестановки.

Есть последовательность M из n~10000 элементов.
Каждай элемент может иметь значения из множества {-1,0,1}.
В связи с определнной особенностью задачи нельзя последовательность записать в троичной системе как число и перебирать инкрементируя число.
Необходим алгоритм, который бы позволял из M получить M' - следующую последовательность, которая бы отличалась от всех предыдущих, полученых этим же алгоритмом. Алгоритм может использовать дополнительные данные, например: номер позиции которую переставили в последний раз.
Нужен:
1) Алгоритм.
2) Как составить начальную последовательность.
3) Какой будет конечная последовательность.
4) И краткие коментарии.


ПС) Ну или хотя бы идеи...

Цитата Cubloid, 08.10.02, 16:50:38

Есть последовательность M из n~10000 элементов.
Каждай элемент может иметь значения из множества {-1,0,1}.
В связи с определнной особенностью задачи нельзя последовательность записать в троичной системе как число и перебирать инкрементируя число.
...

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

Инкрементирование не подходит, потому что в один проход надо сохранить изначальное число 0,1 и -1.
А при инкременте надо будет считать каждый раз количество оных и откидывать лишнее.
Но также еще число большое...
Я придумал алгоритм для 0 и 1:
n=5;
k1=3;

1) Заполняем слева единичками.
11100
2) Нумеруем их.
123
11100
3) 1 двигаются между единицами и ноликами, то есть их последовательность согласно нумерации никогда не меняется и две 1 никогда не меняются местами.
4) Находим первую которая может двигаться.
Перемещаем и запоминаем какую.
11010 3
Находим опять первую которая может двигаться, двигаем.
10110 2
Находим опять первую которая может двигаться, двигаем.
01110 1
5) Но если при предыдущим движением подвинули первую,  то ищем первую какую можно передвинуть, передвигаем ее запоминаем, а все что до нее передвигаем в крайнее левое положение.
11001 3
10101 2
01101 1
Опять тоже самое.
10011 2
01011 1
Опять тоже самое, но слева ничего не осталось вот все.
00111 1
Конец перестановок. Впринципе дополнительное число можно наверное не запоминать.
Соответственно для трех значений я единственное что придумал, так это:
n=6;
k+=3;
k-=2;
1) Сохраняем две последоваетльности, перебираем сначала вторую до конца, сбрасываем, потом передвигаем первую на одну позицию и опять вторую по циклу.

первая    вторая   результат
111000   --0         111--0
111000   -0-         111-0-
111000   0--         1110--

Второй цикл.
110100   --0         11-1-0
110100   -0-         11-10-
110100   0--         1101--
Третий цикл.
101100   --0         1-11-0
101100   -0-         1-110-
101100   0--         1011--
И так далее...
Вроде должно все перебрать, но это медленно, особенно необходимость слияния удручает.
Есть какие-нибудь соображения?
Заранее благодарен...

Все особенности прислал ))

Я понимаю, что не самый простой вопрос и сходу его не решить. Может хоть какие нибудь догадки у кого-то есть.
Помогите, давно уже вопрос мучает.

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

Есть три натуральных числа - начальные условия.
N - длина последовательности.
K+ - количество +1 в последлвательности.
K-  - количество -1 в последлвательности.
________________________________________________
Пример:
N=8; K+=3; K-=2;
{+1,-1,0,0,-1,+1,+1,0} - случайная последовательность составленная на основе представленных выше начальных условий.
_________________________________________________
Необходимо разработать алгоритм, который очень быстро сможет перебрать все возможные УНИКАЛЬНЫЕ последовательности, удовлетворяющие начальным условиям. При этом нельзя сохранить список всех уже найденных последовательностей, а только последнюю.
Не понятно?
Еще проще - перестановки символов в строке, исключая  повторения строки.
Что конкретно не понятно?

Чуть выше я описал свой алгоритм, который удовлетворяет меня, но только для случая из двух элементов 0,1, а для трех {-1,0,+1} я не нашел приемлимого решения, но есть одно описанное тоже выше.

особенность понял, будем думать.. решение обещает быть красивым:)
ЗЫ при инкременте не нужно будет подсчитывать каждый раз кол-во всех 1, -1, 0
достаточно хранить три переменных, в которых будут количества этих элементов... а их при добавлении очередной "1" изменять..
и проверять только их:)

хотя может быть можно как-нить сдвигами.. было нечо похожее по алгебре\%)

Сообщение отредактировано: Demo_S - 11.10.02, 22:02

Что-то я не понимаю, какие там такие особенности. Если в них дело, то надо их, наверное привести. А так инкрементом можно решить в любом случае. Необязательно даже переводить последовательность во что-то еще - достаточно помнить последнюю последовательность, максимально возможный элемент(1) и минимально возможный(-1)

Сообщение отредактировано: Fantasist - 10.10.02, 23:38

Цитата Demo_S, 11.10.02, 00:54:42

ЗЫ при инкременте не нужно будет подсчитывать каждый раз кол-во всех 1, -1, 0
достаточно хранить три переменных, в которых будут количества этих элементов... а их придобаулении очередной 1 изменять..
и проверть только их:)

Прав абсолютно, я так по началу и делал, когда начальные условия состояли только из N.

Если я правильно понял, то можно проходом с вычитом по модулю 3.

2Cubloid
и что , в єтом случае такой способ слишком медленный?
2shalomman что есть вычет по модулю 3?

появилась такая идея.. надо подумать над реализацией.
не знаю насколько она будет быстрой, но приведу:)

запоминаем кол-во "-1", "0" и "1"
пусть "-1" будет m, а нулей будет k, и длина числа (массива) n
нц
  располагаем сначала в нашем массиве все "-1".
  нц
     на оставшиеся места располагаем нули
     (располагаем в массиве длиной n-m нули, и переносим в первый массив)
     
    заполняем оставшиеся места "1"-цами
    работаем с массивом
 
    удаляем из массива все нули и единицы
  кц
 очищаем массив
кц

для реализации нужна функция, которая имея на входе массив, число n длину массива и число m, количество элементов, которые надо расположить, и зная предыдущее расположение, расположит m элементов в массиве. (в этом массиве каждый элемент имеет только 2 значения 0 (не путать с "0")  - элемент в даную ячейку не положен, и 1= в данной ячейке распложен элемент)

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

ЗЫ блин, кривовато получилось... если не понятна мысль, пишите, попробую более ясно ее выразить:)

2Demo_S

это типа xor в тоичной системе исчисления

обьясни пожалуйста вторую часть. я не очень понял. (если не трудно)

думал, над этим троичным xor'om:)... может и можно как-нить, только это не прсолсто будет реализовать имхо.. или я чего-то не понимаю.
фишка в том, что количества "-1", "0" и "1" не должны менятся.


по поводу идеи попытаюсь еще раз коротко и понятненько:)
пусть есть функция, которая может всеми способами разместить m элементов в массиве из n элементов.
n>m

(размещаем например 3 единички в массиве из 5 элементов)
11100
11010
11001
10110
10101
10011
01110
01101
01011
00111

вот.

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

а вот  над реализацией этой функции размещения надо подумать, чтобы она работала быстро...(для работы этой функции придется хранить предыдущее размещение, чтобы она правильно все генерила последующее, причем запомнить только одно предыдущее хватит, тк на его основе можно построить и новое размещение для "0", и новое размещение для "-1".
)

да, естественно, что единицами заполняются все оставщиеся не запоненными места.

понятно/нет?

могу еще пример:)
или надо реализацию этой функции? (над жтим еще не думал:)

Цитата Cubloid, 09.10.02, 12:10:32

Соответственно для трех значений я единственное что придумал, так это:
n=6;
k+=3;
k-=2;
1) Сохраняем две последоваетльности, перебираем сначала вторую до конца, сбрасываем, потом передвигаем первую на одну позицию и опять вторую по циклу.

первая    вторая   результат
111000   --0         111--0
111000   -0-         111-0-
111000   0--         1110--

Второй цикл.
110100   --0         11-1-0
110100   -0-         11-10-
110100   0--         1101--
Третий цикл.
101100   --0         1-11-0
101100   -0-         1-110-
101100   0--         1011--
И так далее...
Вроде должно все перебрать, но это медленно, особенно необходимость слияния удручает.

Demo_S, написанный вами выше вариант, как я понял. Очень похож на приведенный мною выше?
Или я в чем-то не прав?
Спасибо за поддержку.

Цитата Cubloid, 10.10.02, 20:02:38

Есть три натуральных числа - начальные условия.
N - длина последовательности.
K+ - количество +1 в последлвательности.
K-  - количество -1 в последлвательности.
________________________________________________
Пример:
N=8; K+=3; K-=2;
{+1,-1,0,0,-1,+1,+1,0} - случайная последовательность составленная на основе представленных выше начальных условий.
_________________________________________________
Необходимо разработать алгоритм, который очень быстро сможет перебрать все возможные УНИКАЛЬНЫЕ последовательности, удовлетворяющие начальным условиям

Обозначьте "-1" буквой "a", "0" буквой "b", "+1" буквой "c". Вам надо сгенерировать все слова из N букв, в которых буква "a" встречается K_a раз, буква "b" встречается K_b - раз, буква "c" - K_c - раз (K_a + K_b + K_c = N). Так? Но такая задача уже была решена сдесь месяц назад (только там была еще четвертая буква "d", но это неважно). Вот ссылка на решение:

kabilov 12.09.02 10:04:32

http://pascal.sources.ru/cgi-bin/forum/YaBB.cgi?board=algorithm;action=display;num=1031810672