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 :)

Does this answer your question? [Python recursion permutations](https://stackoverflow.com/questions/13109274/python-recursion-permutations) — Yevhen Kuzmovych, Nov 13 '19 at 10:18
Count is for storing the number of occurrences of each character in string. — Vid, Nov 13 '19 at 11:06

ExplodingGayFish · Answer 1 · 2019-11-13T11:11:59.260

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

score 1 · Answer 2 · answered Nov 13 '19 at 12:14

1

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.

answered Nov 13 '19 at 12:14

Filip Młynarski

3,534
1
10
22

Thanks it works. But I am unfamiliar with enumerate. – Vid Nov 13 '19 at 12:50
If you're familiar with [zip()](https://docs.python.org/3/library/functions.html#zip) here's how it could be implemented `zip(range(len(list)), list)`. Also [enumerate() docs](https://docs.python.org/3/library/functions.html#enumerate) – Filip Młynarski Nov 13 '19 at 12:53

score 0 · Answer 3 · answered Nov 13 '19 at 14:02

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)))

How to do recursion precisely in python including lists?

3 Answers3