How would you calculate all possible permutations of 0 through N iteratively?

Question

I need to calculate permutations iteratively. The method signature looks like:

int[][] permute(int n)

For n = 3 for example, the return value would be:

[[0,1,2],  [0,2,1],  [1,0,2],  [1,2,0],  [2,0,1],  [2,1,0]] 

How would you go about doing this iteratively in the most efficient way possible? I can do this recursively, but I'm interested in seeing lots of alternate ways to doing it iteratively.

Answer 1

see QuickPerm algorithm, it's iterative : http://www.quickperm.org/

Edit:

Rewritten in Ruby for clarity:

def permute_map(n)   results = []   a, p = (0...n).to_a, [0] * n   i, j = 0, 0   i = 1   results << yield(a)   while i < n     if p[i] < i       j = i % 2 * p[i] # If i is odd, then j = p[i], else j = 0       a[j], a[i] = a[i], a[j] # Swap       results << yield(a)       p[i] += 1       i = 1     else       p[i] = 0       i += 1     end   end   return results end