Is it possible to output the permutations of 1,...,n using only iterators?

Here a couple of examples in a pseudocode to show what I mean.

This produces the combinations (selections disregarding order without repetition) of 1,...,n taking 3 at a time.

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

The loop works from left to right---for each i, the iterator j will go through its values and for each j, the iterator k will go through its. By adding more variables and changing n, we can generalize w开发者_StackOverflowhat we have above.

Question: can we do the same for permutations? In other words, can we find a way to tweak the iterators to produce the P(n,k)=n!/(p-k)! permutations of 1,...,n? For 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)}]

Use only basic arithmetic operations and things like modular arithmetic, floor/ceiling fcns.

Because this might smell like a homework problem to you, I'd settle on an answer of "yay" or "nay"; your estimate of the difficulty level would be helpful to me as well.

Thank you.

Do you mean generating permutations iteratively, without recursion? Yes, it's possible:

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

See the section "Algorithms to generate permutations"

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].

This follows your restriction to only use basic arithmetic operations (if you don't like the swap, know that you can swap two numbers by using additions and subtractions).

Did you consider using std::next_permutation from <algorithm> ?

At least the source code of any STL implementation should provide you with an answer.

Edit: http://compprog.wordpress.com/tag/permutation/ is a simple pedagogical answer.