How to do recursion precisely in python including lists?

Question

I am a beginner trying to learn recursion in Python. I want to print all the permutations of a given string. For example:

Input: AABC

Output: AABC,AACB,ABAC,ABCA,ACAB,BAAC,BACA,BCAA,CAAB,CABA,CBAA

I have written the following code in Python using recursion.

def foo(str,count):
 result = ""
 while(any(count)):
 for i in range(len(count)):
 if count[i]>0:
 count[i] -= 1
 result = str[i] + foo(str,count)
 print(result)
 return result
s = "AABC"
n = 4
c = {}
for i in range(len(s)):
 if s[i] in c:
 c[s[i]] += 1
 else:
 c[s[i]] = 1
str = list(c.keys())
count = list(c.values())
print(str,count)
foo(str,count)
print(count)

I am getting the output as follows:

['A', 'B', 'C'] [2, 1, 1]

C

BC

ABC

AABC

[0, 0, 0]

It implies that the code is handling only the first case at every level. How can I correct this code?
Any help would be wonderful.
Thanks for your time :)

• Yevhen Kuzmovych: Does this answer your question? Python recursion permutations
• Filip Młynarski: What is count for?
• Vid: Count is for storing the number of occurrences of each character in string.

Answer 1

I'm not sure what you are using count for but here is one way to do it recursively (not very optimal though). :

def foo(s,result):
 if len(result) == 4:
 print(result)
 if len(s) == 0:
 return
 for i in range(len(s)):
 new_s = s.copy()
 del new_s[i]
 foo(new_s,result + s[i])
s = list('AABC')
foo(s,'')

Output:

AABC
AACB
ABAC
ABCA
ACAB
ACBA
AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BAAC
BACA
BCAA
BCAA
CAAB
CABA
CAAB
CABA
CBAA
CBAA

If you want distinct strings, you can add those to a set

Answer 2

Your code look a bit messy and it's hard for me to understand how you tried to solve your problem with it. I tried to create as simple solution as possible to help you understand logic behind creating combinations of any kind of list.

def combinations(x):
 if len(x) == 1:
 yield x
 for idx, i in enumerate(x):
 for comb in combinations(x[:idx]+x[idx+1:]):
 yield i + comb
s = "AABC"
print(list(combinations(s))) # -> ['AABC', 'AACB', 'ABAC', 'ABCA', 'ACAB' ...

x[:idx]+x[idx+1:] here is just short of getting rid of x's element at idx's position. Add a comment if you have any questions so I can help you better understand my solution.

• Vid: Thanks it works. But I am unfamiliar with enumerate.
• Filip Młynarski: If you're familiar with zip() here's how it could be implemented zip(range(len(list)), list). Also enumerate() docs

Answer 3

I figured out something which works but it gives duplicate answers because of multiple occurrences of character 'A', hence I used set() to get the desired answer.

def foo(s,l,result):
 if len(result)==4:
 l.append(result)
 for i in range(len(s)):
 foo(s[0:i]+s[i+1:],l,result+s[i])
s = "AABC"
l = []
r = foo(s,l,"")
print(list(set(l)))