DFS 打印 python 中字符串的所有排列

Question

我正在使用 DFS 打印所有排列，但我有一个小的 pythonic 错误 w.r.t。 return 来自 foo 的值。

对于键 '1'，我希望 foo 的 return 值为 [[1,2,3] [1,3,2]] 但目前为 [1,2, 3,1,3,2]。我尝试使用 result.append 但它没有用。

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

基本上我不想使用多余的最后两行代码。

Answer 1

而不是 return output 你应该做 return [output]，这样收集的数字就会放在自己的列表中。然后，当您执行 result += 时，您将不会添加单个数字，而是添加列表，这就是您想要的。

请注意，您对字典的使用过于复杂，并且只会为第一级带来好处，因为每个键都包含除一个以外的所有值，因此您将迭代除一个以外的所有值，这并不多收获。

除了 itertools has methods 满足您的需求之外，您还可以使用 set 来跟踪哪些值仍然可供选择：

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)

DFS 打印 python 中字符串的所有排列

DFS to print all permutations of a string in python

python

algorithm

depth-first-search