Implementing Heap's Algorithm for Permutations in Python

Question

I'm trying to implement Heap's algorithm in python, but having trouble with it repeating some of the solutions. I'm stumped with where the bug is at. Here is the implementation:

import copy

def _permute(l, n):
    if n == 1:
        print(l)
    else:
        for i in range(n - 1):
            # note: must copy here, or all answers will be same
            new_arr = copy.copy(l)
            _permute(new_arr, n - 1)

            if n % 2 == 0:
                l[i], l[n - 1] = l[n - 1], l[i]
            else:
                l[0], l[n - 1] = l[n - 1], l[0]

        _permute(l, n - 1)

For the input [0, 1, 2] and 3, I get:

[0, 1, 2]
[1, 0, 2]
[2, 1, 0]
[1, 2, 0]
[0, 1, 2] ** repeats from first answer **
[1, 0, 2] ** repeats from second answer **

With the last 2 results, repeating from first and second, missing:

[0, 2, 1]
[2, 0, 1]

I've searched multiple places and tried different implementations of this algorithm, but no matter how many times I try, I can't seem to get it to work. What am I missing?

Answer 1

You were placing your recursive call in the wrong place, this should do the trick (and you shouldn't use the copy):

def _permute(l, n):
    if n == 1:
        print(l)
    else:
        _permute(l, n - 1)
        for i in range(n - 1):
            if n % 2 == 0:
                l[i], l[n - 1] = l[n - 1], l[i]
            else:
                l[0], l[n - 1] = l[n - 1], l[0]

            _permute(l, n - 1)