Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Перестановки

Автор: NoliX 5.4.2007, 20:57

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

Автор: maxim1000 5.4.2007, 21:39

можно попробовать сначала сделать генерацию всех перестановок в нужном порядке, а потом добавить в алгоритм отсечение тех, которые не удовлетворяют критерию

Автор: Artemios 6.4.2007, 00:39

NoliX, можно уточнить, что в задаче понимается под лексикографическим порядком на числах? Или упорядочиваемые объекты -- не числа? Объясню, в связи с чем вопрос. Обычно лексикография задается для объектов, представляющих из себя некоторую комбинацию более простых объектов, для которых уже определены бинарные отношения <,>,=. Это могут быть строки, состоящие из символов, векторы с числовыми компонентами и т.д. тогда если  a=(a1,a2,...,an), b=(b1,b2,...,bn), то a меньше b по лексикографическому порядку (a<b),  если существует i (1<=i<=n) такое, что для всех t<i выполняется at=bt, но ai<bi. А числа -- это вроде бы простые объекты, не имеющие в своем составе иных более простых, причем на них уже существует естественный порядок. Что может пониматься под их лексикографическим упорядочением?

Автор: NoliX 6.4.2007, 16:30

Цитата можно попробовать сначала сделать генерацию всех перестановок в нужном порядке, а потом добавить в алгоритм отсечение тех, которые не удовлетворяют критерию гы, я ж сказал Цитата Естественно перебор всех перестановок, а затем выделение из них вышеописанных не подходит Цитата NoliX, можно уточнить, что в задаче понимается под лексикографическим порядком на числах? Или упорядочиваемые объекты -- не числа? Объясню, в связи с чем вопрос. Обычно лексикография задается для объектов, представляющих из себя некоторую комбинацию более простых объектов, для которых уже определены бинарные отношения <,>,=. Это могут быть строки, состоящие из символов, векторы с числовыми компонентами и т.д. тогда если  a=(a1,a2,...,an), b=(b1,b2,...,bn), то a меньше b по лексикографическому порядку (a<b),  если существует i (1<=i<=n) такое, что для всех t<i выполняется at=bt, но ai<bi. А числа -- это вроде бы простые объекты, не имеющие в своем составе иных более простых, причем на них уже существует естественный порядок. Что может пониматься под их лексикографическим упорядочением? Над этим я что-то даже не задумывался))) Мне было сказано перестановки чисел 1,2,3,...,n тоесть тупо по возрастанию, тоесть перестановка из 3-х элеметов это 123 132 213 231 312 321

Автор: maxim1000 6.4.2007, 19:49

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

Автор: NoliX 6.4.2007, 23:15

Цитата я имел в виду, добавить отсечение не после алгоритма генерации, а _в него_ т.е. как только у нас появляется нечётное число на чёном месте, например, - сразу выбрасывать от варианта с генерацией всех перестановок и последующим фильтрованием это отличается тем, что перестановки, не удовлетворяющие критерию на первых индексах, даже не будут сгенерированы Сорри, я может не так тебя понял, хотя какая разница, оба алгоритма работают за o(n!), а вот мой алгоритм основанный на слиянии перестановок четных элеметов с перестановками нечетных элементов работает за (([n/2]!)^3), на сколько я правильно посчитал (что кстати заметно меньше при n>4)? но это если сначала генерировать, а потом пересекать каждую из четных с каждой из нечетных, а если генерировать сразу на месте, то вообще ([n/2]!), осталось только прикрутиnm правильную коммбинацию, чтобы получился лексикографический порядок, а вот как это сделать, вообще никакого понятия не имею( Хотя может тут вообще иной подход имеется... Препод сказал, что это очень сложная задача, корректно генерировать такие перестановки за минимально возможное число операций (понятно, что можно черти как посливать эти перестановки, а затем отсортировать)

Автор: Artemios 7.4.2007, 02:11

Цитата(NoliX @  6.4.2007,  17:30 ) Над этим я что-то даже не задумывался))) Мне было сказано перестановки чисел 1,2,3,...,n тоесть тупо по возрастанию, тоесть перестановка из 3-х элеметов это 123 132 213 231 312 321 Угу, понял. Тебе нужно не внутри одной перестановки лекс. порядок иметь, а нужно, чтобы сами перестановки (которые, в общем-то, являются векторами/массивами, т.е. составными объектами) выдавались в лекс. порядке. Цитата(NoliX @  7.4.2007,  00:15 ) понятно, что можно черти как посливать эти перестановки, а затем отсортировать а может процессе генерации производить не просто слитие очередной перестановки, а вставку в упорядоченный список (или даже лучше в бинарное дерево)? Добавлено через 1 минуту и 32 секунды хотя лучше лекс. внимательнее покрутить, здесь что-то попроще должно быть.

Автор: maxim1000 7.4.2007, 09:08

имелось в виду вот что: пусть есть у нас алгоритм, который генерирует перестановки таким образом: сначала - все, начинающиеся с 1, потом - с 2, потом - с 3 и т.д. внутри каждого такого шага - похожее поведение т.е. для первого шага будет генерировать сначала с 12 в начале, потом с 13, с 14 и т.д. генерирует он их в лексикографическом порядке за O(n!) теперь мы вносим ограничение - чётные на чётных, нечётные на нечётных получаем алгоритм, генерирующий такие перестановки в таком порядке: 1..., 3..., 5... и т.д. 1... генерируется так: 12..., 14..., 16... и т.д. внесение ограничения на первом уровне уменьшает количество работы в 2 раза внесение на каждом следующем, вроде бы, тоже таким образом получаем O(n!/2^n) это, кажется, эквивалентно O(([n/2]!)^2)

Автор: NoliX 7.4.2007, 18:50

Так, всем спасибо, сейчас подумаю, результаты соих раздумий выложу, потом еще вместе подумаем)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)