DFS to print all permutations of a string in python

Question

I am using DFS to print all the permutations but I have a small pythonic mistake w.r.t. return value from foo.

For the key '1', I want the return value of foo to be [[1,2,3] [1,3,2]] but it is currently [1,2,3,1,3,2]. I tried using result.append but it didn't work.

data = [1, 2, 3]

def foo(key, dict_data, output):
  result = []
  if len(output) == len(dict_data.keys()):
    return output
  values = dict_data[key]
  for value in values:
    if value not in output:
      result += foo(value, dict_data, output + [value])
  return result

dict_data = {}
for i in range(len(data)):
  dict_data[data[i]] = data[0:i] + data[i+1:]
result = []
for key in dict_data.keys():
  result += foo(key, dict_data, [key])
for i in range(0, len(result), len(data)):
  print(result[i:i+len(data)])

Basically I don't want to use the last 2 lines of my code which is superfluous.

Answer 1

Instead of return output you should do return [output], so that the gathered numbers are put in their own list. Then when you do result += you will not be adding individual numbers, but the list, which is what you want.

Note that your use of a dictionary is overly complex, and only brings benefit for the first level, because each key includes all values except one, so you'll be iterating all values except one, which is not much of a gain.

Apart from the fact that itertools has methods for what you want, you could use a set to keep track of which values are still available for selecting:

def foo(set_data, output):
  if len(set_data) == 0:
    return [output]
  result = []
  for value in set_data:
    result += foo(set_data - set([value]), output + [value])
  return result

data = [1, 2, 3]
set_data = set(data)
result = foo(set_data, [])
print(result)