Permutate a string letters recursively in python

Posted on by mohamad wael

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
    1. 'ab' ->['ab','ba']
  • if it contains three characters it must return a list containing the permutation of these three characters ,
    1. 'abc'->
    2. [
    3. 'abc' , 'acb' , 'bac', 'bca' , 'cab' , 'cba'
    4. ]

    the solution for this problem recursively is the following

  1. ''' 
  2.     [] -> []
  3.     [a] -> [a]
  4.     [a,b]

  6.         [a] + [b]
  7.         [b] + [a]

  9.     [a,b,c]
  10.         [a] + [b,c]
  11.                 [a] + [b] + [c]
  12.                 [a] + [c] + [b]
  13.         [b] + [a,c]
  14.                 [b] + [a] + [c]
  15.                 [b] + [c] + [a]
  16.         [c] + [a,b]
  17.                 [c] + [a] + [b]
  18.                 [c] + [b] + [a]
  19.       
  20. '''


  23. def permutateString(string):
  24.     if len(string) == 0:
  25.         return []
  26.     if len(string) == 1:
  27.         return [string]
  28.     # enumerate throuhh the string reusievly
  29.     result = []
  30.     for index, char in enumerate(string):
  31.         result.extend(
  32.             [char + _string for _string in permutateString(string[0:index] + string[index+1:])])
  33.     return result


  36. if __name__ == '__main__':
  37.     print(permutateString(''))
  38.     print(permutateString('a'))
  39.     print(permutateString('ab'))
  40.     print(permutateString('abc'))
  41.     print(permutateString('abcd'))
  42.     print(permutateString('O*H_'))

  44. /*
  45. output
  46. []
  47. ['a']
  48. ['ab', 'ba']
  49. ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
  50. ['abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba']
  51. ['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']

  53. */
Related Posts: