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

Question

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 what 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 as a homework problem to you, I'd be happy with an answer of yay or nay or perhaps also the level of difficulty (which is relative, I know.)

Thank you.

Answer 1

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.

Answer 2

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