Skip to main content
 首页 » 编程设计

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

2025年04月02日9birdshome

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

  • 模式 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']] # 注意:[['B', 'A']] 在我的问题中是一样的

请您参考如下方法:

您可以使用递归函数,它采用模式中的第一个数字,并从剩余项目中生成该长度的所有组合。然后递归剩余的模式和项目以及生成的前缀。一旦您使用了模式中的所有数字,只需 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。