language-agnostic - 您将如何迭代计算 0 到 N 的所有可能排列？

Question

我需要迭代计算排列。方法签名如下所示:
int[][] permute(int n)
对于 n = 3例如，返回值将是:

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

您将如何以最有效的方式迭代地执行此操作？我可以递归地执行此操作，但我有兴趣看到许多以迭代方式执行此操作的替代方法。

Answer 1

参见 QuickPerm 算法，它是迭代的:http://www.quickperm.org/

编辑:

为清楚起见，用 Ruby 重写:

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