查找數組和組合模式的組合

Question

我有這樣的數組，每個模式指定組合形狀，每個數字代表組合的大小。

• 圖案0：[1, 1, 1, 1]
• 圖案1：[2, 1, 1]
• 圖案2：[3, 1]
• 圖案3：[4]
• ...

我也有一個char值列表如下所示。 len（chars）等於上面數組的值的總和。

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

我想找到字符的所有組合給定模式下。例如，對於模式1，4C2 * 2C1 * 1C1是組合的數量。我不知道如何創建這樣的組合數組。當然我知道python中有很多有用的組合函數。但我不知道如何使用它們來創建組合數組。

EDITED

我很抱歉，我的解釋是混亂的。我給出一個簡單的例子。

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

注意上面，因爲它使用yield from只與Python 3工作。