Как перебирать перестановки

[Профессор Снэйп]

Дано $n \approx 20$, надо перебрать все элементы группы $S_n$ и для каждого кое-что проверить.

Не могу понять, как организовать перебор множества перестановок. Единственное, что пришло в голову --- перебирать всех отображения из $\{ 1, \ldots, n \}$ в $\{ 1, \ldots, n \}$, для каждого проверять инъективность и если отображение оказалось перестановкой, делать с ним то, что нужно. Но уж больно медленно оно работает. Всё-таки $20^{20}$ гораздо больше, чем $20!$

[gris]

а Вам нужно все перебрать или сделать случайную выборку? Их почти квинтиллион. Многовато будет.

[creative]

Незнаю, правильно ли я Вас понимаю, но вот:

http://en.wikipedia.org/wiki/Permutatio ... rmutations

Так же есть у Кнута в "Конкретной математике", но с ходу найти не получается.

[12d3]

Надо упорядочить все перестановки в лексикографическом порядке (имеется в виду запись перестановки как $(a_1,a_2,...,a_n)$, где $i$-й элемент переходит на место $a_i$), а потом явно указать правило перехода к следующей перестановке. Правило такое:
Находим ближайшую к концу пару элементов, в котором следующий элемент меньше предыдущего (пусть это пара $a_k, a_{k+1},\,\, a_k<a_{k+1}$), теперь переставляем элементы с $k$-го по $n$-ый в таком порядке: на $k$-е место ставим наименьший элемент, больший $a_k$, а остальные располагаем в порядке возрастания.
Начинается перебор перестановок с тождественной, заканчивается перестановкой вида $(a_n,a_{n-1}...a_2,a_1)$
P.S. Если программируете на C++, то в STL есть функция next_permutation(), которая самостоятельно проделывает все вышеописанное.

[creative]

12d3

Спасибо. Теперь вспомнил источник, вот "Generating All Tuples and Permutations". The Art of Computer Programming. 4, Fascicle 2. (сноска в статье вики, там же про лексикографический порядок)

[Профессор Снэйп]

gris в сообщении #362361 писал(а):

а Вам нужно все перебрать или сделать случайную выборку?

Перебрать

На самом деле там всё обозримо... Ещё не дописал, но думаю, будет работать за приемлемое время. Дело в том, что многие перестановки будут отбраковываться по значениям на пяти-шести первых аргументах, так что в дереве надо обходить не квинтильон вершин, а поменьше.

[venco]

Профессор Снэйп в сообщении #362378 писал(а):

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

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

[Профессор Снэйп]

venco в сообщении #362383 писал(а):

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

Ага, так и делаю

[Day]

Нашел у себя вот такую программку.
Это правда для N=6, но думаю, Вам не составит большого труда переделать ее для N=20
Взято из книги В.Липского "Комбинаторика для программистов"

#include <stdio.h>
#define N 6

main()
{ char s[N+1], t; int i, j, r, k;

 for(i=0; i<N; i++) s[i] = '1'+i;
 s[N] = '\0';

 while(1) {
   printf("%s\n", s);
       // Находим самое правое место, где s[i] < s[i+1]
   for(i=N-1; i>=0 && s[i] > s[i+1]; i--) ;
   if (i<0) break; // Уже получили "654321" - самую старшую перестановку
       // Находим s[j] - наименьший элемент справа от s[i] и больший его
   for(j=N-1; s[i] > s[j]; j--) ;
       // Меняем s[i] <-> s[j]
   t = s[j];
   s[j] = s[i];
   s[i] = t;
       // То, что за "i" - переворачиваем
   for(k=i+1, r=N-1; r > k; k++, r--) {
     t = s[r];
     s[r] = s[k];
     s[k] = t;
   }
 }
}