# 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']
['abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba']
['O*H_', 'O*_H', 'OH*_', 'OH_*', 'O_*H', 'O_H*', '*OH_', '*O_H', '*HO_', '*H_O', '*_OH', '*_HO', 'HO*_', 'HO_*', 'H*O_', 'H*_O', 'H_O*', 'H_*O', '_O*H', '_OH*', '_*OH', '_*HO', '_HO*', '_H*O']

*/```