|
Придумал алгоритм короче в реализации (как мне представляется) - рекурсивный:
Пусть существует способ способ получить (n-1)! перестановок для (n-1) элементов.
Способ получить перестановки для n элементов, где новый элемент обозначим как "K", следующий:
1) выводим все последовательности типа (K A1 A2 A3 ... An-1). для каждой из (A1 A2 A3 ... An) - (n-1)! перестановок
2) выводим все последовательности типа (A1 K A2 A3 ... An-1)...
...
n) выводим все последовательности типа (A1 A2 A3 ... An-1 K).
Таким образом мы выведем (n-1)!*n=n! последовательностей, все последовательности различны и состоят из n различных элементов. Таким образом доказано, что таким способом выводятся все последовательности.
P.S. Можно использовать сдвиг, т.е. из (K A1 A2 A3 ... An-1) последовательности получить последовтельности вида (A1 A2 A3 ... An-1 K ), (A2 A3 ... An-1 K A1). (A3 ... An-1 K A1 A2), ... , (An-1 K A1 A2 ... An-2), но так, ИМХО, сложнее.
Добавление: Первый алгоритм сохраняет лексиграфический порядок, второй (рекурсивный) - не сохраняет.
|