4. Write recursive function q4(inString) that implements the algorithm below, and returns a list of all permutations of the input string (i.e. all the possible arrangements of the string's characters). Presume that all the characters in the input are different (so all of the permutations will be different.)

For example, >>> q4("b") ['b'] >>> q4("ab") ['ab', 'ba'] >>> q4("zab") ['zab', 'azb', 'abz', 'zba', 'bza', 'baz'] >>> q4("dcba") ['dcba', 'cdba', 'cbda', 'cbad', 'dbca', 'bdca', 'bcda', 'bcad', 'dbac', 'bdac', 'badc', 'bacd', 'dcab', 'cdab', 'cadb', 'cabd', 'dacb', 'adcb', 'acdb', 'acbd', 'dabc', 'adbc', 'abdc', 'abcd'] 

ALGORITHM:

# if the string has just one character: # It is the only perm. Return it in a list # else: # Use a recursive call to get alist of the permutations # of the "tail" of the string, i.e.string[1:] # Then, for item in the list above, # create result permutations by "inserting" string[0] at each possible # index position 0...len(input string), adding each of these # result permutations to a result list that you are building. # Return the list of all of the result permutations. # # E.g. If the input is "abcd" # the list the tail's permutations is ["bcd", "cbd", "cdb", "bdc", "dbc", "dcb"] # Then, when working with, say, "cbd" from that list, we # generate "acbd", "cabd", "cbad", and "cbda" by "inserting" 'a' at # each possible position, 0-3, in "cbd"

4. Write recursive function q4inString) that implements the algorithm below, and returns a list of all permutations of the input string (i.e. all the possible arrangements of the string's characters). Presume that all the characters in the input are different (so all of the permutations will be different.) For example, >>> 94("6") ['b'] >>> 94("ab") ['ab', 'ba'] >>> 94("zab") ['zab', 'azb', 'abz', 'zba', 'bza', 'baz'] >>> q4("dcba") ['dcba', 'cdba', 'cbda', 'cbad', 'dbca', 'bdca', 'bcda', 'bcad', 'dbac', 'bdac', 'badc', 'bacd', 'dcab', 'cdab', 'cadb', 'cabd', 'dacb', 'adcb', 'acdb', 'acbd', 'dabc', 'adbc', 'abdc', 'abcd'] ALGORITHM: # if the string has just one character: # It is the only perm. Return it in a list else: Use a recursive call to get alist of the permutations of the "tail" of the string, i.e.string[1:] Then, for item in the list above, create result permutations by "inserting" string[0] at each possible index position 0... len(input string), adding each of these result permutations to a result list that you are building. Return the list of all of the result permutations. # E.g. If the input is "abcd" the list the tail's permutations is ["bcd", "cbd", "cdb", "bdc", "dbc", "dcb"] Then, when working with, say, "cbd" from that list, we generate "acbd", "cabd", "cbad", and "cbda" by "inserting" 'a' at each possible position, 0-3, in "cbd