python all possible permutation using recursion

Question

How can I implement the recursive way to write the permutation of an string? For example, if the input is 'abc', I want my result to be:

[a', 'b', 'c', 'd', 'e', 'aa', 'ab', 'ac', 'ad', 'ae', 'ba',
 'bb','bc', 'bd', 'be', 'ca', 'cb', 'cc', 'cd', 'ce', 'da', 'db',
 'dc','dd', 'de', 'ea', 'eb', 'ec', 'ed', 'ee', 'aaa', 'aab', 'aac',
 'aad','aae', 'aba', 'abb', 'abc', 'abd', 'abe', 'aca', 'acb',
 'acc'....]

In addition, if a string from the result is also contained in an another list, then return that string. For example 'a' and 'b' are in [a,aaah,aahed,aahing,aahs,'b'], I want to display the 'a' and 'b'.

Edit

I tried to use a for loop, but I get a MemoryError.

def perm(l,last,result)
    if len(result[-1]==len(l)):
        return result
    else:
        for i in l:
            for u in last:
                last.append(u+i)
         result.extend(last)
    perm(l,last,result)
    return result

perm(['a','b','c'],[''],[''])

Can you make an attempt first? You are more likely to get help if you do. — paisanco, Jun 02 '15 at 03:31
@kurenaiKunai I takes me a while to figure out how to type codes on stack overflow. I have edited my questions to include my codes. — BlackS, Jun 02 '15 at 04:13
[http://stackoverflow.com/questions/8371887/making-all-possible-combinations-of-a-list-in-python][1] — Kurenai Kunai, Jun 02 '15 at 05:21

score 0 · Accepted Answer · answered Jun 02 '15 at 05:52

Generate all strings of the current length and then look for longer strings recursively.

def perm(chars, prefix):
    result = []
    if len(prefix) < len(chars):
        for char in chars:
            result.append(prefix + char)
        for char in chars:
            result.extend(perm(chars, prefix + char))
    return result

print perm(["a", "b", "c"], "")

python all possible permutation using recursion

1 Answers1