Heap permutation list

Question

I tried to write my heap's permutation algo in python and for some reason when I print them directly in the reccurasion it workes fine. The problem begins once I try to add them all in to a list.

permutations = []


def permutation(to_permute, k):
    if k == 1:
        print(to_permute)  # this works
        permutations.append(to_permute)   # this doesn't
    else:
        permutation(to_permute, k - 1)
        for i in range(k - 1):
            if k % 2 == 0:
                to_permute[k - 1], to_permute[i] = to_permute[i], to_permute[k - 1]
            else:
                to_permute[0], to_permute[k - 1] = to_permute[k - 1], to_permute[0]
            permutation(to_permute, k - 1)


permute = [0, 1, 2]
permutation(permute, 3)
print(permutations)

Output :

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

see https://stackoverflow.com/questions/2612802/list-changes-unexpectedly-after-assignment-how-do-i-clone-or-copy-it-to-prevent — Wups, Oct 31 '20 at 10:44

score 2 · Accepted Answer · answered Oct 31 '20 at 10:40

2

All your permutations are references to the same list object that you keep modifying. The simplest fix is appending shallow copies instead:

permutations.append(to_permute[:])

answered Oct 31 '20 at 10:40

user2390182

72,016
6
67
89

Heap permutation list

1 Answers1