查找具有数组和组合模式的组合

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

请注意，上面只适用于Python3，因为它使用的是yield from。