使用数组和组合模式查找组合

Question

我有这样的数组，每个图案指定一个组合形状，每个数字代表组合的大小。

模式 0：[1, 1, 1, 1]
模式 1：[2, 1, 1]
模式 2：[3, 1]
模式 3：[4]
...

我还有一个如下所示的字符值列表。 len(chars) 等于上数组值的总和。

chars = ['A', 'B', 'C', 'D']

我想查找遵循给定模式的所有字符组合。例如，对于模式 1，4C2 * 2C1 * 1C1 是组合数。

[['A', 'B'], ['C'], ['D']]
[['A', 'B'], ['D'], ['C']]
[['A', 'C'], ['B'], ['D']]
[['A', 'C'], ['D'], ['B']]
[['A', 'D'], ['B'], ['C']]
[['A', 'D'], ['C'], ['B']]
...

但我不知道如何创建这样的组合数组。我当然知道 python 中有很多组合的有用函数。但是我不知道如何使用它们来创建组合数组。

已编辑

很抱歉我的解释令人困惑。我举个简单的例子。

模式 0：[1, 1]
模式 1：[2]
chars = ['A', 'B']

那么，结果应该如下所示。所以第一维应该是排列，第二维应该是组合。

pat0: [['A'], ['B']]
pat0: [['B'], ['A']]
pat1: [['A', 'B']] # NOTE: [['B', 'A']] is same in my problem

Answer 1

您可以使用递归函数，该函数采用模式中的第一个数字，并根据剩余项目生成该长度的所有组合。然后递归剩余的模式和项目以及生成的前缀。一旦您使用了模式中的所有数字，只需 yield 前缀一直到呼叫者：

from itertools import combinations

pattern = [2, 1, 1]
chars = ['A', 'B', 'C', 'D']

def patterns(shape, items, prefix=None):
    if not shape:
        yield prefix
        return

    prefix = prefix or []
    for comb in combinations(items, shape[0]):
        child_items = items[:]
        for char in comb:
            child_items.remove(char)
        yield from patterns(shape[1:], child_items, prefix + [comb])

for pat in patterns(pattern, chars):
    print(pat)

输出：

[('A', 'B'), ('C',), ('D',)]
[('A', 'B'), ('D',), ('C',)]
[('A', 'C'), ('B',), ('D',)]
[('A', 'C'), ('D',), ('B',)]
[('A', 'D'), ('B',), ('C',)]
[('A', 'D'), ('C',), ('B',)]
[('B', 'C'), ('A',), ('D',)]
[('B', 'C'), ('D',), ('A',)]
[('B', 'D'), ('A',), ('C',)]
[('B', 'D'), ('C',), ('A',)]
[('C', 'D'), ('A',), ('B',)]
[('C', 'D'), ('B',), ('A',)]

请注意，上面仅适用于 Python 3，因为它使用的是 yield from.

使用数组和组合模式查找组合

Find combinations with arrays and a combination pattern

python

combinations

permutation