我需要迭代计算排列。方法签名如下所示:
int[][] permute(int n)
为了n = 3例如,返回值将是:
[[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]]
您将如何以最有效的方式迭代进行此操作?我可以递归执行此操作,但是我有兴趣看到许多其他迭代执行方法。
请参阅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