This may sound very simple, I tried searching for the solution but couldn't find it hence posting the question. Appreciate the help, Thanks in advance.
I am trying to print all the subsequences of a given list/string in python using recursion. Below is the output I expect:
Given Input list : [1,3,2]
Output List : [[],[1],[3],[2],[1,2],[1,3],[3,2],[1,3,2]]
This is what I have tried:
def printSubsequences(ind,ans,l,n):
final_ans = []
if ind == n:
return ans
else:
ans.append(l[ind])
final_ans.extend(printSubsequences(ind 1,ans,l,n))
ans.pop()
final_ans.extend(printSubsequences(ind 1,ans,l,n))
return final_ans
print(printSubsequences(0,[],[1,3,2],3))
Output of above code: [1, 3, 2, 1, 3, 1, 2, 1, 3, 2, 3, 2]
The output is correct partially as It does not contain []
(empty subset), but I want it in specified format as aforementioned. I also tried append
method but that is giving Output : [[[[], []], [[], []]], [[[], []], [[], []]]]
.
I don't understand what I am doing wrong here, Can someone explain - Why append
is failing and extend
is working, and How can I get my desired output ?
CodePudding user response:
You have run into this classic python trap:
When you append ans
to the list of results, it's always a reference to the same list ans
, not a copy. So when you call ans.pop()
, you erase the last element of that list, and it is removed in all subsequences. Try for instance this code:
a = [2]
b = [a, a, a]
print(b) # [[2], [2], [2]]
a.pop()
print(b) # [[], [], []]
The workaround is to adopt a more functional style, never modifying the ans
list in-place, and rather building a new list when needed for the recursive calls:
def subsequences(ind,ans,l,n):
final_ans = []
if ind == n:
return [ans]
else:
final_ans.extend(subsequences(ind 1,ans [l[ind]],l,n))
final_ans.extend(subsequences(ind 1,ans,l,n))
return final_ans
>>> subsequences(0, [], [1,2,3], 3)
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
Notable modifications:
- I renamed the function
subsequences
rather thanprintSubsequences
, since it doesn't print; - I fixed the base case which should be
return [ans]
, notreturn ans
; - I replaced the calls to
ans.append
andans.pop
with