Generation of all possible permutations using backtracking

Question

I am new to programming and I was going through some basic backtracking problems. One of these was to print all possible permutations of a list. I got the following code from the internet.

def permutation(arr,size,n):
    if size == 1:
        print(arr)
        return
    for i in range(size):
        permutation(arr,size-1,n)
        if size & 1:
            arr[0],arr[size-1] = arr[size-1],arr[0]
        else:
            arr[i],arr[size-1] = arr[size-1],arr[i]

This is working fine and it printed the following output for input arr = [1,2,3]

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

Now I want to store all these possible permutations into a different array and for that modified the code into this.

 ans = []
 def permutation(arr,size,n):
    if size == 1:
        ans.append(arr)
    for i in range(size):
        permutation(arr,size-1,n)
        if size & 1:
            arr[0],arr[size-1] = arr[size-1],arr[0]
        else:
            arr[i],arr[size-1] = arr[size-1],arr[i]

But when I printed the list and, it printed this.

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

What am I doing wrong here? How can I store all the possible permutations into a list?

After `if size == 1:` you have `return` in the first code, but **not** in the second code — Jan Stránský, Aug 25 '20 at 17:49
Does this answer your question? [List of lists changes reflected across sublists unexpectedly](https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly) — superb rain, Aug 25 '20 at 17:52
People still upvoting duplicates of the most duplicated Python question. Weird. — superb rain, Aug 25 '20 at 17:54
@superbrain the problem here is using two seemingly same code, that are actually not the same. In this sense, it is not duplicate — Jan Stránský, Aug 25 '20 at 17:56
@JanStránský The only non-duplicate here is the same list object stuffed into the result list over and over again. Same problem as in that other question. — superb rain, Aug 25 '20 at 18:01
@superbrain I see two question. "How can I store all the possible permutations into a list?" this is for sure duplicate. But "What am I doing wrong here?" deserves an answer — Jan Stránský, Aug 25 '20 at 18:02
change `ans.append(arr)` to `ans.append(arr[:])` and `return` afterwards. — Chris Charley, Aug 25 '20 at 18:04
@ChrisCharley Interestingly, the `return` doesn't appear to be needed. — superb rain, Aug 25 '20 at 18:06

Jan Stránský · Answer 1 · 2020-08-25T18:18:01.920

0

Original answer, not answering the question (see edit)

Answering the "What am I doing wrong here?" question.

You have

    if size == 1:
        print(arr)
        return

in the first code, but

    if size == 1:
        ans.append(arr)

Try:

    if size == 1:
        ans.append(arr)
        return

and it should work as expected

EDIT:

thanks to @superbrain for criticism, it really did not work, I was too optimistic about code correctness in the OP.

So the answer for "What am I doing wrong here?" is this line

        ans.append(arr)

where you append the same instance of list every time, so you end with list of the same objects

It is similar to this scenario:

list1 = [1,2,3]
list2 = []
list2.append(list1)
list2.append(list1)
print(list2) # [[1, 2, 3], [1, 2, 3]]
list1[2] = 9
print(list2) # [[1, 2, 9], [1, 2, 9]]

edited Aug 25 '20 at 18:18

answered Aug 25 '20 at 17:58

Jan Stránský

1,671
1
11
15

"should" as in you haven't tested it? – superb rain Aug 25 '20 at 18:01
Yes, I could use "must" instead of "should". Some circumstances are (should be? :-) clear without testing – Jan Stránský Aug 25 '20 at 18:04
You're right, it was clear that this won't fix it, but I tested it anyway. – superb rain Aug 25 '20 at 18:07
Your change doesn't have any effect other than preventing burning a few more CPU cycles. – superb rain Aug 25 '20 at 18:16

zardosht · Accepted Answer · 2020-08-27T09:13:46.203

The problem is that you always append a reference to the same instance of the arr object (which is a list) to the ans list. See this question for a similar situation.

You don't have this problem in the first code, because you simply print the list at each permutation. But in the second code you manipulate the same list at every recursion, and when you are at top of you recursion tree you get back the original list ([1, 2, 3]).

To solve the problem, you can add a deep copy of you your list to the ans:

def permutation(arr, size, n):
    if size == 1:
        # ans.append(arr)

        # this copies every element of arr into a 
        # new list and then appends the new list to ans.
        ans.append([e for e in arr]) 

    for i in range(size):
        permutation(arr, size-1, n)
        if size & 1:
            arr[0], arr[size-1] = arr[size-1], arr[0]
        else:
            arr[i], arr[size-1] = arr[size-1], arr[i]

score -1 · Answer 3 · answered Aug 25 '20 at 18:02

Backtracking is a general algorithm "that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution." (Wikipedia).

So, basically, what you do is build incrementally all permutations. As soon as as you build a single permutation, you backtrack and build another one, and so on until you generate all n! possible permutations, say, on n symbols.

Example: n=3, S={1,2,3}.

You start with 1. Then you move forward an choose 2 (since 1 has already been chosen), and then you choose 3. At that point you have built the first permutation 123. Then you backtrack and select 3 instead of 2, then select 2, and you have 132. You backtrack again, but you have already used 2 and 3, so you backtrack again (one level up where), and choose 2 instead of 1, then you select 1, and finally 3, so you have 213.

Generation of all possible permutations using backtracking

3 Answers3