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?
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]