Heap's algorithm是一种系统的循环方式 N 元素的所有排列“一次交换”。对于奇数 N, 它特别整洁,因为最后的排列似乎只是 一次交换不同于第一个排列。
但是,即使对于 N,这种环绕也不会发生。例如,对于 N=4,排列顺序为:
1234
2134
3124
1324
2314
3214
4213
2413
1423
4123
2143
1243
1342
3142
4132
1432
3412
4312
4321
3421
2431
4231
3241
2341
那么,有没有人有一个交换算法,它可以循环 N 次? 如果不是,那么 N=4 怎么样?
最佳答案
通过检查,满足约束的一种可能序列是:
1234
1432
3412
4312
1342
3142
4132
4231
2431
3421
4321
2341
3241
1243
2143
4123
1423
2413
4213
3214
2314
1324
3124
2134
1234
在每一步应该只有两个元素被交换。
对于较大的 N,我建议您尝试实现 Steinhaus–Johnson–Trotter algorithm我相信这将仅使用相邻元素的交换来生成这些排列,并且会让您离开初始位置一个交换。
基于 rosetta code 的 Python 代码:
N=4
def s_permutations(seq):
def s_perm(seq):
if not seq:
return [[]]
else:
new_items = []
for i, item in enumerate(s_perm(seq[:-1])):
if i % 2:
new_items += [item[:i] + seq[-1:] + item[i:]
for i in range(len(item) + 1)]
else:
new_items += [item[:i] + seq[-1:] + item[i:]
for i in range(len(item), -1, -1)]
return new_items
return [(tuple(item), -1 if i % 2 else 1)
for i, item in enumerate(s_perm(seq))]
for x,sgn in s_permutations(range(1,N+1)):
print ''.join(map(str,x))
关于algorithm - 修改堆的生成排列的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23277518/