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

language-agnostic, math, permutation

Solution

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

Problem

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.

Original source

Related problems