Heap's Algorithm producing the same permutation twice

Question

I am currently implementing Heaps's Algorithm in Python, but my current solution is returning some of the permutations twice.

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"])

This code produces the following results:

['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

Since I do not want repeated results,

What am I doing wrong?

Answer 1

According to Heap's Algoritm, your loop should be iterating over startingIndex and not the length of the list.

You should also make the same recursive call after the for loop, and not just at the beginning of it.

This fixed version works for your example:

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