我目前正在用 Python 实现堆算法,但我目前的解决方案是将一些排列返回两次。
def generate(startingIndex, alist):
if startingIndex == 1:
print(alist)
else:
for i in range(0, len(alist)):
generate(startingIndex - 1, alist)
if i % 2 == 1:
alist[0], alist[startingIndex - 1] = alist[startingIndex - 1], alist[0]
else:
alist[i], alist[startingIndex - 1] = alist[startingIndex - 1], alist[i]
generate(3, ["a", "b", "c"])
此代码产生以下结果:
['a', 'b', 'c'] #this will be repeated
['b', 'a', 'c']
['a', 'b', 'c'] #here
['b', 'c', 'a'] #this will be repeated
['c', 'b', 'a']
['b', 'c', 'a'] #here
['c', 'a', 'b'] #this will be repeated
['a', 'c', 'b']
['c', 'a', 'b'] #here
因为我不想要重复的结果,
我做错了什么?
最佳答案
根据 Heap's Algoritm ,您的循环应该遍历 startingIndex
而不是列表的长度。
您还应该在 for
循环之后进行相同的递归调用,而不仅仅是在它的开头。
此固定版本适用于您的示例:
def generate(startingIndex, alist):
if startingIndex == 1:
print(alist)
else:
for i in range(startingIndex - 1):
generate(startingIndex - 1, alist)
if i % 2 == 1:
alist[0], alist[startingIndex - 1] = alist[startingIndex - 1], alist[0]
else:
alist[i], alist[startingIndex - 1] = alist[startingIndex - 1], alist[i]
generate(startingIndex - 1, alist)
generate(3, ['a', 'b', 'c'])
关于python - 堆算法两次产生相同的排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53519184/