Алгоритм кучи, производящий одну и ту же перестановку дважды

Question

В настоящее время я реализую алгоритм Heaps в 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

Так какЯ не хочу повторных результатов,

Что я делаю не так?

Answer 1

Согласно Алгоритму кучи , ваш цикл должен повторяться по 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'])