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?

hbejgel · Accepted Answer · 2020-04-01 21:03:27Z

2

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)

answered Apr 1, 2020 at 21:03

hbejgel

4,8772 gold badges19 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

rici Over a year ago

How does the order of the recursive calls differ in your solution? The key is to not do the copy.

jth_92 Over a year ago

While it modified the 'l' argument in the function and would print out correctly, it wouldn't modify the original invocation of it. My solution was to create a new array and append the result of l to it, but if I didn't copy all the values would be the same. The key was to move the copy from the for loop into the if n == 1 statement: ` if n == 1: new_arr = copy.copy(l) result.append(new_arr) ` This worked! Thanks so much! I was about to toss the computer out of the window.

Collectives™ on Stack Overflow

Implementing Heap's Algorithm for Permutations in Python

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related