python - 如何获得所有可能的排列？

Question

我有一个嵌套列表

x = [['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]

我想在不超出相应子列表的情况下对子列表中的元素进行所有可能的排列。 预期的输出是这样的变化:

[['c', 'b', 'a'], ['d'], ['f', 'e', ['g', ['i', 'h']]]]
[['d'], ['a', 'b', 'c'], ['f', 'e', [['h', 'i'], 'g']]]

每个元素都必须保留在它的方括号中。

我写了这个生成器:

def swap(x):
    if isinstance(x, list):
        res = np.random.choice(x, len(x), replace = False)
        return [list(map(ff, res))]

    else:
        return x

它给出了预期结果的随机变体，但我需要将它们全部收集起来。我该怎么做？我应该怎么做:

my_list = []
for i in range(10000): # not necessary 10000, any huge number
    my_list.append(ff(yy1))

然后将 unique 函数应用于 my_list 以选择唯一的，或者还有其他选择？

Answer 1

isinstance()+itertools.permutations() 是一个很好的方向，只需要它们的乘积，以及一些跟踪哪个排列适用于哪个部分树(？)(我正在考虑生成树的所有可能遍历):

import itertools

def plan(part,res):
  if isinstance(part,list) and len(part)>1:
    res.append(itertools.permutations(range(len(part))))
    for elem in part:
      plan(elem,res)
  return res

def remix(part,p):
  if isinstance(part,list) and len(part)>1:
    coll=[0]*len(part)
    for i in range(len(part)-1,-1,-1):
      coll[i]=remix(part[i],p)
    mix=p.pop()
    return [coll[i] for i in mix]
  else:
    return part

def swap(t):
  plans=itertools.product(*plan(t,[]))
  for p in plans:
    yield remix(t,list(p))

for r in swap([['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]):
  print(r)

plan() 递归地找到所有“真正的”列表(其中有多个元素)，并为它们创建 itertools.permutations()。

swap() 调用 plan()，然后使用 itertools.product()

remix() 为单个 megapermutation 步骤创建一个实际对象。这有点复杂，因为我不想与跟踪树位置作斗争，而是 remix() 向后工作，转到最后一个列表，并将其与当前列表的最后一个组件混合计划，将其从列表中删除。

虽然您的示例有点长，但它似乎有效，输入更简单，输出更易于管理:

for r in swap([['a', ['b', 'c']], ['d'], 'e']):
  print(r)

[['a', ['b', 'c']], ['d'], 'e']
[['a', ['c', 'b']], ['d'], 'e']
[[['b', 'c'], 'a'], ['d'], 'e']
[[['c', 'b'], 'a'], ['d'], 'e']
[['a', ['b', 'c']], 'e', ['d']]
[['a', ['c', 'b']], 'e', ['d']]
[[['b', 'c'], 'a'], 'e', ['d']]
[[['c', 'b'], 'a'], 'e', ['d']]
[['d'], ['a', ['b', 'c']], 'e']
[['d'], ['a', ['c', 'b']], 'e']
[['d'], [['b', 'c'], 'a'], 'e']
[['d'], [['c', 'b'], 'a'], 'e']
[['d'], 'e', ['a', ['b', 'c']]]
[['d'], 'e', ['a', ['c', 'b']]]
[['d'], 'e', [['b', 'c'], 'a']]
[['d'], 'e', [['c', 'b'], 'a']]
['e', ['a', ['b', 'c']], ['d']]
['e', ['a', ['c', 'b']], ['d']]
['e', [['b', 'c'], 'a'], ['d']]
['e', [['c', 'b'], 'a'], ['d']]
['e', ['d'], ['a', ['b', 'c']]]
['e', ['d'], ['a', ['c', 'b']]]
['e', ['d'], [['b', 'c'], 'a']]
['e', ['d'], [['c', 'b'], 'a']]

符合预期的 24 个排列