CODEWITHSUNDEEP
pythonalgorithmpermutationheaps-algorithm
winged hussar
winged hussar

Reputation: 21

Heap's Algorithm producing the same permutation twice

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?

Upvotes: 1

Views: 400

Answers (1)

Omer Tuchfeld
Omer Tuchfeld

Reputation: 3042

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

Upvotes: 2

Related Questions