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

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

然后将独特的功能应用于my_list到select独特的，或者还有其他选择？

Answer 1

不是特别 pythonic，但我会通过查找索引的排列来处理它，如下所示：


from itertools import permutations
mylist= [[1], [1,2], [1,2,3]]
combinations = list(permutations([i for i in range(len(mylist))]))

print(combinations)

for item in combinations:
  print([mylist[item[i]] for i in range(len(mylist))])

Output:
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
[[1], [1, 2], [1, 2, 3]]
[[1], [1, 2, 3], [1, 2]]
[[1, 2], [1], [1, 2, 3]]
[[1, 2], [1, 2, 3], [1]]
[[1, 2, 3], [1], [1, 2]]
[[1, 2, 3], [1, 2], [1]]

Answer 2

您是否考虑过使用 itertools？

有可用的显式组合和排列工具

来自docs：

itertools.permutations(iterable[, r])

Return successive r length permutations of elements in the iterable.

If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.

Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.

Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each permutation.

itertools.combinations(iterable, r)

Return r length subsequences of elements from the input iterable.

Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each combination.

Answer 3

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() 递归地找到所有 "real" 列表（其中有一个以上的元素），并为它们创建 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 个排列，符合预期

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

How to get all possible permutations?

python

loops

permutation

combinatorics

python-3.x