0

I want to generate a list of all permutations of a string using a backtracking algorithm.

I modified some code from a previous post: https://stackoverflow.com/a/20955291/12021192 

def permutations(string, step = 0):

    permTrack = []

    if step == len(string):
        permTrack.append(''.join(string))

    for i in range(step, len(string)):
        string_copy = list(string)
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]
        permutations(string_copy, step + 1)

    return permTrack

permTrack = permutations('ABC')

I expected permTrack = ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA], but the actual output is permTrack = [ ].

The idea is to is to append to a list permTrack at the base case, when step == len(string). This works for instance in the original code to print the permutations.

Can someone help me figure this out?

Matthew Cha
  • 3
  • 2

1 Answers1

0

You don't do anything with what is returned by permutations when it is called recursively.

If you add what gets returned to permTrack, you should get what you want.

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • I see my mistake, also a previous answer that was deleted was helpful. I modified my code by adding a new parameter in the function: def permutations(string, step = 0, permTrack = [ ]). Then, deleting permTrack = [ ] in the function body. This produces the desired output. Thanks. – Matthew Cha Sep 04 '19 at 18:35
  • You don't need a new parameter; you just need to take what gets returned by `permutations` in the recursive call and add its elements to what is in `permTrack`. – Scott Hunter Sep 04 '19 at 18:37