python 列表拆分的组合

Question

给定两个输入参数：

x: <list> 喜欢 [0, 1, 2, 3]

splits: <list> of int 表示拆分的数量和长度，如 [1, 2, 1]。这意味着列表必须分成 3 个，第一个包含 1 个元素，第二个包含 2 个元素，第三个包含 1 个元素

我需要一个 returns 所有可能的拆分组合的函数，例如：

def get_combos(x, splits): ...

>>> get_combos([0, 1, 2, 3], [1, 2, 1])

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

输入将总是满足这些条件：

min(splits) >= 1 --> split中总有一个元素
sum(splits) == len(x) --> x中的所有元素都被取

递归执行此操作的最佳方法是什么？

Answer 1

您可以使用递归生成器函数：

def combos(a, b, c = []):
   if not a or not b:
      yield [*map(tuple, c)]
   else:
      for x, y in enumerate(a):
         if not c or len(c[-1]) == b[0]:
            yield from combos(a[:x]+a[x+1:], b[1:] if c else b, c+[[y]])
         else:
            yield from combos(a[:x]+a[x+1:], b, [*c[:-1], c[-1]+[y]])

print(list(combos([0, 1, 2, 3], [1, 2, 1])))

输出：

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

python 列表拆分的组合

python combinations of split of list

python

recursion

combinations

combinatorics