产生相同排列twi的Heap算法

Question

我目前正在用Python实现Heaps的算法，但是我目前的解决方案是两次返回一些排列。你知道吗

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

因为我不想重复结果

我做错什么了？你知道吗

Answer 1

根据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'])