# Permutate a string letters recursively in python

Let us say we have a string and we want to permutate through its letter . So for example

• if the string is empty it will return an empty list
• if it contains only one characters it must return a list containing only one character `'a' ->['a']`
• if it contains two characters it must return a list containing the permutation of these characters
`'ab' ->['ab','ba']`
• if it contains three characters it must return a list containing the permutation of these three characters ,
```'abc'->
[
'abc' , 'acb' , 'bac', 'bca' , 'cab' , 'cba'
]```

the solution for this problem recursively is the following

```'''
[] -> []
[a] -> [a]
[a,b]

[a] + [b]
[b] + [a]

[a,b,c]
[a] + [b,c]
[a] + [b] + [c]
[a] + [c] + [b]
[b] + [a,c]
[b] + [a] + [c]
[b] + [c] + [a]
[c] + [a,b]
[c] + [a] + [b]
[c] + [b] + [a]

'''

def permutateString(string):
if len(string) == 0:
return []
if len(string) == 1:
return [string]
# enumerate throuhh the string reusievly
result = []
for index, char in enumerate(string):
result.extend(
[char + _string for _string in permutateString(string[0:index] + string[index+1:])])
return result

if __name__ == '__main__':
print(permutateString(''))
print(permutateString('a'))
print(permutateString('ab'))
print(permutateString('abc'))
print(permutateString('abcd'))
print(permutateString('O*H_'))

/*
output
[]
['a']
['ab', 'ba']
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']