Print Permutations of Array in Python

Question

Apologies in advance as this question has been repeated ad nauseum.

I've banged my head for 3+ hours on what should be simple, but just cannot figure this out. If anyone can tell me what's going wrong I'll grant you naming rights to my first born.

outputs = []
def permutation_helper(available_list, slate):
    if len(available_list) == 0:
        outputs.append(slate)
        return
    for num_idx in range(len(available_list)):
        slate.append(available_list[num_idx])
        if num_idx == len(available_list) - 1:
            permutation_helper(available_list[0:num_idx], slate)
        else:     
            permutation_helper(available_list[0:num_idx] + available_list[num_idx+1:], slate)
        slate = slate[0:len(slate)-1]
slate = []
nums = [1,2,3]
permutation_helper(nums, slate)

print(outputs)

Instead of the normal set of permutations, the result is

[[1, 2, 3], [1, 2, 3, 2], [1, 2, 2, 1, 3], [1, 2, 2, 1, 3, 1], [1, 2, 2, 1, 3, 1, 2], [1, 2, 2, 1, 3, 1, 2, 1]]

I added some print statements when the slate is changed, and it seems like it is being changed two times from [1,2,3] to [1,2] instead of just once.

Code with debugging statements

outputs = []
def permutation_helper(available_list, slate):
    print("Starting with available list: " + str(available_list) + "and slate: " + str(slate))
    if len(available_list) == 0:
        print("Adding to output")
        outputs.append(slate)
        return
    for num_idx in range(len(available_list)):
        print("Starting iteration")
        print("Appending " + str(available_list[num_idx]) + " to slate of: " + str(slate))
        slate.append(available_list[num_idx])
        if num_idx == len(available_list) - 1:
            print("Calling last")
            permutation_helper(available_list[0:num_idx], slate)
        else:     
            print("Calling default")
            permutation_helper(available_list[0:num_idx] + available_list[num_idx+1:], slate)
        print("Slate was: " + str(slate) + " and will be: "+ str(slate[0:len(slate)-1]))
        slate = slate[0:len(slate)-1]
        print("Ending iteration with available list of " + str(available_list))
    print("Ending call for available list:  " + str(available_list))
slate = []
nums = [1,2,3]
permutation_helper(nums, slate)

Output

Starting with available list: [1, 2, 3]and slate: []
Starting iteration
Appending 1 to slate of: []
Calling default
Starting with available list: [2, 3]and slate: [1]
Starting iteration
Appending 2 to slate of: [1]
Calling default
Starting with available list: [3]and slate: [1, 2]
Starting iteration
Appending 3 to slate of: [1, 2]
Calling last
Starting with available list: []and slate: [1, 2, 3]
Adding to output
Slate was: [1, 2, 3] and will be: [1, 2]
Ending iteration with available list of [3]
Ending call for available list:  [3]
Slate was: [1, 2, 3] and will be: [1, 2]
Ending iteration with available list of [2, 3]
Starting iteration
Appending 3 to slate of: [1, 2]
Calling last
Starting with available list: [2]and slate: [1, 2, 3]
Starting iteration
Appending 2 to slate of: [1, 2, 3]
Calling last
Starting with available list: []and slate: [1, 2, 3, 2]
Adding to output
Slate was: [1, 2, 3, 2] and will be: [1, 2, 3]
Ending iteration with available list of [2]
Ending call for available list:  [2]
Slate was: [1, 2, 3, 2] and will be: [1, 2, 3]
Ending iteration with available list of [2, 3]
Ending call for available list:  [2, 3]
Slate was: [1, 2, 3] and will be: [1, 2]
Ending iteration with available list of [1, 2, 3]
Starting iteration
Appending 2 to slate of: [1, 2]
Calling default
Starting with available list: [1, 3]and slate: [1, 2, 2]
Starting iteration
Appending 1 to slate of: [1, 2, 2]
Calling default
Starting with available list: [3]and slate: [1, 2, 2, 1]
Starting iteration
Appending 3 to slate of: [1, 2, 2, 1]
Calling last
Starting with available list: []and slate: [1, 2, 2, 1, 3]
Adding to output
Slate was: [1, 2, 2, 1, 3] and will be: [1, 2, 2, 1]
Ending iteration with available list of [3]
Ending call for available list:  [3]
Slate was: [1, 2, 2, 1, 3] and will be: [1, 2, 2, 1]
Ending iteration with available list of [1, 3]
Starting iteration
Appending 3 to slate of: [1, 2, 2, 1]
Calling last
Starting with available list: [1]and slate: [1, 2, 2, 1, 3]
Starting iteration
Appending 1 to slate of: [1, 2, 2, 1, 3]
Calling last
Starting with available list: []and slate: [1, 2, 2, 1, 3, 1]
Adding to output
Slate was: [1, 2, 2, 1, 3, 1] and will be: [1, 2, 2, 1, 3]
Ending iteration with available list of [1]
Ending call for available list:  [1]
Slate was: [1, 2, 2, 1, 3, 1] and will be: [1, 2, 2, 1, 3]
Ending iteration with available list of [1, 3]
Ending call for available list:  [1, 3]
Slate was: [1, 2, 2, 1, 3] and will be: [1, 2, 2, 1]
Ending iteration with available list of [1, 2, 3]
Starting iteration
Appending 3 to slate of: [1, 2, 2, 1]
Calling last
Starting with available list: [1, 2]and slate: [1, 2, 2, 1, 3]
Starting iteration
Appending 1 to slate of: [1, 2, 2, 1, 3]
Calling default
Starting with available list: [2]and slate: [1, 2, 2, 1, 3, 1]
Starting iteration
Appending 2 to slate of: [1, 2, 2, 1, 3, 1]
Calling last
Starting with available list: []and slate: [1, 2, 2, 1, 3, 1, 2]
Adding to output
Slate was: [1, 2, 2, 1, 3, 1, 2] and will be: [1, 2, 2, 1, 3, 1]
Ending iteration with available list of [2]
Ending call for available list:  [2]
Slate was: [1, 2, 2, 1, 3, 1, 2] and will be: [1, 2, 2, 1, 3, 1]
Ending iteration with available list of [1, 2]
Starting iteration
Appending 2 to slate of: [1, 2, 2, 1, 3, 1]
Calling last
Starting with available list: [1]and slate: [1, 2, 2, 1, 3, 1, 2]
Starting iteration
Appending 1 to slate of: [1, 2, 2, 1, 3, 1, 2]
Calling last
Starting with available list: []and slate: [1, 2, 2, 1, 3, 1, 2, 1]
Adding to output
Slate was: [1, 2, 2, 1, 3, 1, 2, 1] and will be: [1, 2, 2, 1, 3, 1, 2]
Ending iteration with available list of [1]
Ending call for available list:  [1]
Slate was: [1, 2, 2, 1, 3, 1, 2, 1] and will be: [1, 2, 2, 1, 3, 1, 2]
Ending iteration with available list of [1, 2]
Ending call for available list:  [1, 2]
Slate was: [1, 2, 2, 1, 3, 1, 2] and will be: [1, 2, 2, 1, 3, 1]
Ending iteration with available list of [1, 2, 3]
Ending call for available list:  [1, 2, 3]
[[1, 2, 3], [1, 2, 3, 2], [1, 2, 2, 1, 3], [1, 2, 2, 1, 3, 1], [1, 2, 2, 1, 3, 1, 2], [1, 2, 2, 1, 3, 1, 2, 1]]

If I understood correctly, I think you are trying to replicate the Heap's algorithm for permutations. Why don't you compare with the original to find your differences? Also duplicate of stackoverflow.com/questions/60975877/… — decadenza
– decadenza, Commented Sep 11, 2022 at 16:05

Lenormju · Accepted Answer · 2022-09-12 10:22:06Z

I am sorry for you, indeed this a head-banging bug. The problem lies in the interaction between 2 aspects of Python : the local/global scopes, and the mutable/immutable references.
Both are tricky in isolation, combined they are nasty.

What happens is that you have a global variable named slate, exactly like the slate argument of your function, also exactly like the slate variable declared with slate = slate[0:len(slate)-1]. What is especially disturbing is that on this line :

slate = slate[0:len(slate)-1]

both slates are not the same references ... not all the time ... Let me explain with a (not that much) simpler example inspired by your code :

from typing import List, Any


def my_function(mutable_arg: List[Any], level: int = 0):
    indent_str = ' |' * level
    print(indent_str, f"{id(mutable_arg)=!r} {mutable_arg=!r}")
    if level >= 2:
        return
    else:
        for x in ('a', 'b',):
            print(indent_str, f"currently at {level=!r} calling subfunction")
            mutable_arg.append(x + str(level))
            my_function(mutable_arg, level=level+1)
            print(indent_str, f"back at {level=!r}")
            print(indent_str, f"{id(mutable_arg)=!r} {mutable_arg=!r} before pop")
            mutable_arg = mutable_arg[:len(mutable_arg)-1]
            print(indent_str, f"{id(mutable_arg)=!r} {mutable_arg=!r} after pop")


mutable_arg = []  # whatever
print(f"top-level {id(mutable_arg)=!r} {mutable_arg=!r}")
my_function(mutable_arg)

it produces (with my manual annotations) :

top-level id(mutable_arg)=140026485211520 mutable_arg=[]       # here we have our initial list id=...1520
#                                    ^^^^
 id(mutable_arg)=140026485211520 mutable_arg=[]                # the reference is passed to the function (in other languages, we call that "pass by reference")
 currently at level=0 calling subfunction
 | id(mutable_arg)=140026485211520 mutable_arg=['a0']          # still the same
 | currently at level=1 calling subfunction
 | | id(mutable_arg)=140026485211520 mutable_arg=['a0', 'a1']  # still the same
 | back at level=1
 | id(mutable_arg)=140026485211520 mutable_arg=['a0', 'a1'] before pop  # still the same
 | id(mutable_arg)=140026485571904 mutable_arg=['a0'] after pop  # here it changes !! it becomes id=...1904 !
#                             ^^^^
 | currently at level=1 calling subfunction
 | | id(mutable_arg)=140026485571904 mutable_arg=['a0', 'b1']    # stays at the new value id=1904
 | back at level=1
 | id(mutable_arg)=140026485571904 mutable_arg=['a0', 'b1'] before pop  # stays
 | id(mutable_arg)=140026485939904 mutable_arg=['a0'] after pop  # another new value ! id=...9904
#                             ^^^^
 back at level=0
 id(mutable_arg)=140026485211520 mutable_arg=['a0', 'a1'] before pop  # and here is initial value again ! id=...1520
 id(mutable_arg)=140026485939904 mutable_arg=['a0'] after pop  # but it changes immediatly to id=...9904
[...snip]

At first, because Python is pass-by-reference for mutable objects (like lists), the function receives a reference to the list defined at the top-level (global) scope.
But when we encounter the mutable_arg = mutable_arg[...] for the first time, the (right-side) mutable_arg still not exists in the local scope so Python grabs the global reference. Then mutable_arg[:len(mutable_arg)-1] returns a new reference (a slice). But when we assign it to (left-side) mutable_arg then Python stores it in the local scope (which is the current function call execution). So effectively, this line creates a different copy of mutable_arg. On the following iterations, each time mutable_arg is referenced, Python finds it in the local scope so it does not use the global one anymore. From there, we are effectively working on a branched-off version. In itself, it would not be a problem, but the caller expects mutable_arg to be in the same state as before the call (unchecked invariant). But because of the branching, the last element was removed only in the copy only, not in the original. Hence the diverging.

The fix is simply to change the line to :

- slate = slate[0:len(slate)-1]
+ slate.pop()

That way, it always operates on the same reference, it never creates a new one, so slate can't diverge.

Another solution is to copy the slates before passing them to the sub-functions :

permutation_helper(available_list[0:num_idx], slate.copy())
#                                                  ^^^^^^^
permutation_helper(available_list[0:num_idx] + available_list[num_idx+1:], slate.copy())
#                                                                               ^^^^^^^

Collectives™ on Stack Overflow

Print Permutations of Array in Python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related