您将如何迭代计算从0到N的所有可能排列? [英] How would you calculate all possible permutations of 0 through N iteratively?
本文介绍了您将如何迭代计算从0到N的所有可能排列?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我需要迭代计算置换.方法签名如下:
I need to calculate permutations iteratively. The method signature looks like:
int[][] permute(int n)
例如对于n = 3
,返回值将是:
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.
推荐答案
请参阅QuickPerm算法,它是迭代的: http://www.quickperm.org/
see QuickPerm algorithm, it's iterative : http://www.quickperm.org/
为清楚起见,在Ruby中进行了重写:
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
这篇关于您将如何迭代计算从0到N的所有可能排列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文