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

[kalapanga]

Проверять. Как обычно - короткий выбрать. n переменное, где-то до 10-15 объектов. Время перебора в худшем случае выходит за рамки желаемого. Вот и хочется сократить по возможности.

[Vince Diesel]

Зачем тогда что-то изобретать. Стоит взять эффективный алгоритм нахождения всех перестановок, и для каждой организовать цикл проверок с вставлением дополнительного элемента, как я писал выше. Вместо $1$ можно взять $n$ и добавлять справа, пока этот элемент правее $n-1$. Если перестановка хранится в виде списка, то вставить элемент легко. Либо походу организовать постоение маршрута с вставкой. Никаких лишних действий в этом алгоритме вроде нет.

[kalapanga]

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

Зачем тогда что-то изобретать. Стоит взять эффективный алгоритм нахождения всех перестановок, и для каждой организовать цикл проверок с вставлением дополнительного элемента, как я писал выше. Вместо $1$ можно взять $n$ и добавлять справа, пока этот элемент правее $n-1$. Если перестановка хранится в виде списка, то вставить элемент легко. Либо походу организовать постоение маршрута с вставкой. Никаких лишних действий в этом алгоритме вроде нет.

Я все-таки не очень понял, что и куда ты предлагаешь вставлять. Из примера видно, что 1 не всегда левее 2. А вот вставить в известный алгоритм генерации перестановок проверку, что крайний правый элемент больше крайнего левого - это может и на самом деле достаточно будет. Проверю.

[Vince Diesel]

Берем алгоритм для нахождения всех перестановок из 3х элементов. Затем для каждой перестановки в цикле добавляем по очереди $4$ на каждое место правее 3. Получим:
$\{1,2,3\}\to\{1,2,3,4\}$,
$\{1,3,2\}\to\{1,3,2,4\},\{1,3,4,2\}$,
$\{2,1,3\}\to\{2,1,3,4\}$,
$\{2,3,1\}\to\{2,3,1,4\},\{2,3,4,1\}$,
$\{3,1,2\}\to\{3,1,2,4\},\{3,1,4,2\},\{3,4,1,2\}$,
$\{3,2,1\}\to\{3,2,1,4\},\{3,2,4,1\},\{3,4,2,1\}$.

[kalapanga]

Спасибо, понял! До меня на "живых" цифрах лучше доходит! :)
Всем спасибо за идеи! Пошел воплощать.