Можно ли вывести перестановки 1, ..., n, используя только итераторы?

Question

Вот пара примеров в псевдокоде, чтобы показать, что я имею в виду.

В результате получается комбинация (выборки без учета порядка без повторений) из 1, ..., n по 3.

Do[Print[i,j,k], {i,1...n-2}, {j,i+1...n-1}, {k,j+1...n}]

Цикл работает слева направо - для каждого i итератор j просматривает свои значения, а для каждого j итератор k проходит через его. Добавляя больше переменных и меняя n, мы можем обобщить то, что имеем выше.

Вопрос: можем ли мы сделать то же самое для перестановок? Другими словами, можем ли мы найти способ настроить итераторы для получения P (n, k) = n! / (P-k)! перестановки 1, ..., п? Для k = 3

Do[Print[i,j,k], {i, f_1 , g_1(i,n)}, {j, f_2(i), g_2(i,j,n)}, {k, f_3(i,j), g_3(i,j,k,n)}]

Используйте только основные арифметические операции и такие вещи, как модульная арифметика, функции пола / потолка.

Поскольку это может пахнуть для вас домашним заданием, я бы остановился на ответе «да» или «нет»; Ваша оценка уровня сложности также будет полезна для меня.

Спасибо.

Answer 1

Вы имеете в виду генерацию перестановок итеративно, без рекурсии?Да, это возможно:

http://en.wikipedia.org/wiki/Permutation

См. Раздел «Алгоритмы генерации перестановок»

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

В соответствии с вашим ограничением использовать только основные арифметические операции (есливам не нравится своп, знайте, что вы можете поменять местами два числа, используя сложения и вычитания).

Answer 2

Рассматривали ли вы использование std::next_permutation из <algorithm>?

По крайней мере, исходный код любой реализации STL должен дать вам ответ.

Редактировать: http://compprog.wordpress.com/tag/permutation/ простой педагогический ответ.