Получить все перестановки исключая "симметричные"

[kalapanga]

Извиняюсь за возможно ненаучную терминологию, но постараюсь объяснить свою проблему понятно.
Есть множество неповторяющихся объектов. Необходимо получить все перестановки элементов, но исключая "симметричные" (наверное они как-то правильно называются?). Т.е. 1-3-2-4 и 4-2-3-1 считаем одинаковыми. Грубо говоря это маршруты обхода, и безразлично - обходить слева направо или справа налево. Остается половина.
Алгоритмов генерации перестановок нашел достаточно (и с рекурсией, и без).
Существует ли алгоритм, позволяющий сгенерировать сразу только "несимметричные" перестановки?
Получить все, а потом отсеивать лишние - не очень интересно, т.к. конечная цель ускорение перебора.

[Sonic86]

Как-то неполно объяснили. Вы считаете симметричными некоторые цепочки - откуда берутся цепочки из множества объектов. Т.е. вот у Вас есть 6 объектов и Вы объединяете $1,2,3,4$ в цепочку $1-2-3-4$ и $5,6$ в цепочку $5-6$ (и считаете их симметричными). По какому принципу Вы их объединяете в цепочки?

[kalapanga]

У меня перестановка в классическом понимании. Я привел пример одной из пар для множества из 4-х объектов.
Для трех объектов "одинаковые" пары это:
123 321
132 231
213 312
Мне хочется алгоритм который бы выдавал мне не все 6 перестановок, а только три. Какая из пары попадет - не важно.

[Sonic86]

Ааа, понял. Щас попробую подумать

[Vince Diesel]

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

[Sender]

Цитата:

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

Боюсь, это не выход. Так, перестановки 1,3,4,2 и 2,4,3,1 окажутся в одной половине.

[kalapanga]

Vince Diesel в сообщении #472820 писал(а):

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

Это, к сожалению, неверно. Лексикографический порядок не подходит (проверяется опытным путем).
Наверное, в этом и будет решение - найти правильный порядок генерации. У меня что-то пока не выходит.

[Vince Diesel]

Хм, тогда рекурсивно. Сначала есть перестановка $\{1,2\}$. Теперь допустим, уже есть набор перестановок для $n$ элементов. Чтобы получить перестановки для случая $n+1$, следующий элемент вставляется на 1-е, 2-е, ... , $n+1$-е места. Если бы при таком построении на $n+1$ шаге получились бы две одинаковых перестановки, то при удалении $(n+1)$-го элемента, имелись бы одинаковые перестановки из $n$ элементов.

[Azog]

Ну я бы предложил это делать следующим образом. Генерируем перестановки в виде дерева. Дерево, поясню на примере. Пусть ищем перестановки из чисел 1,2,3. В верхней вершине стоит 0, далее отходит 3 ребра, соединяющие с вершинами. на которых написано соответственно 1, 2, 3. От единицы отходит 2 ребра, соединяющие с вершинами, на которых написано 2 и 3. От двойки - еще одно ребро у тройке, от тройки к двойке. Ребра, соответственно направленые. Получаем дерево, глубиной 4. Всевозможные пути по ребрам - это все перестановки. Далее, из дерева выкидываем симметричные пути. Т.е. на 123, выкинем нижний лист от тройки, ведущий к единице и т.д.. По сути дела, это "умный" перебор. Вообще задачу хорошо бы конкретизировать: что именно Вы хотите от алгоритма. Эффективность по количеству действий, памяти?

[kalapanga]

Azog в сообщении #472880 писал(а):

Всевозможные пути по ребрам - это все перестановки. Далее, из дерева выкидываем симметричные пути. Т.е. на 123, выкинем нижний лист от тройки, ведущий к единице и т.д.. По сути дела, это "умный" перебор. Вообще задачу хорошо бы конкретизировать: что именно Вы хотите от алгоритма. Эффективность по количеству действий, памяти?

Из этих перестановок нужно будет выбрать "наилучшую". Хочу сократить перебор в два раза. Наибольший выигрыш по скорости получится если сразу генерировать только "несимметричные" перестановки, а не получать все с последующим их разбором.

[Vince Diesel]

Кстати, конструкция в моем предыдущем посте наводит на мысль, что это в точности все перестановки, в которых 1 левее 2. Так что можно взять все перестановки из $\{2,\ldots,n\}$, а затем для каждой добавлять единицы по очереди на все места левее двойки.

[vvvv]

Проще всего, по-моему, использовать алгоритм вертикальной прогонки и затем взять половину (первую или вторую) всех перестановок.
Примеры могу привести.

[vvvv]

..

[kalapanga]

Vince Diesel в сообщении #472937 писал(а):

Кстати, конструкция в моем предыдущем посте наводит на мысль, что это в точности все перестановки, в которых 1 левее 2. Так что можно взять все перестановки из $\{2,\ldots,n\}$, а затем для каждой добавлять единицы по очереди на все места левее двойки.

1 левее 2 ключевой момент! Кажется я нужный порядок нашел! Привожу пример для 4-х элементов:
1 3 4 2
1 4 3 2
1 2 4 3
1 4 2 3
1 2 3 4
1 3 2 4

2 1 4 3
2 4 1 3
2 1 3 4
2 3 1 4

3 1 2 4
3 2 1 4
Главную роль играют первый и последний элемент в перестановке! Номер последнего должен быть больше номера первого. Поэтому с 1 перестановок больше всего, с 2 меньше, с 3 еще меньше, а с 4 нет вообще.
А между первым и последним элементом все возможные перестановки из оставшихся элементов множества. (В моем примере их по две)
Вроде так? Ошибок не видать? Теперь это запрограммировать красивенько осталось!

[Vince Diesel]

А какое по порядку величины предполагается $n$? И в чем цель, проверять маршруты или выдавать список перестановок?