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']

*/