python - 如何获得数组的组合，条件是每种类型的元素至少有 4 个(或每种类型的 x)？

Question

我正在尝试编写一个 python 函数来获取输入数组的长度 n 的所有组合，其中每种类型的特定元素至少有 4 个(或某些 # x )(下面的示例)

input = ['m1','m2','m3','m4','m5','m6','t1','t2','t3','t4','t5','t6','w1','w2','w3','w4','w5','w6']

输出 = 组合列表，其中每种类型的元素至少有 4 个(即，如果这些元素全部存在，则一周中的每一天都有 4 个(如果为 0，则无关紧要))

对于 itertools.combinations(input_array, 12) 中的组合:

例如，从输入数组中，n=12 的有效输出如下

out = ['m1','m2','m3','m4,','t3','t4,'t5','t6','w1','w2','w3','w4']

而它生成的无效输出将是

out = ['m1','m2','m3','t2','t3','t4,'t5','t6','w1','w2','w3','w4']

是否有一种更有效的方法来生成每种类型至少有 4 个的组合(即 4 个带有“m”的条目、4 个带有“t”的条目、4 个带有“w”的条目)。现在我只是循环遍历所有组合它来了，如果它通过了检查，我就把它放入一个数组中，但是对于较大的输入数组，这可能需要很长时间。如果除了组合之外还有其他方法也可以。

编辑以澄清其他需求，我意识到我没有提供一些关键信息。

任何输入数组最多可以有七种不同类型的元素。这使我变得更加复杂，因为当我只需要 12 个元素(每种类型至少 4 个如果存在)时，另外必须保留引用原始输入的顺序每种元素类型的数组(这是一个奖励，如果不能完成也没关系)。

示例输入可以是 = [m1,m2,m3,m4,m5,m6,m7,m8,m9,m10,m11,m12,t1,t2,t3,t4,w1,w2,w3,w4,f1,f2,f3 ，f4]。

有效输出:

[m1,m2,m3,m4,m5,m6,m7,m8,m9,m10,m11,m12](可以是所有一种类型，因为其他类型不存在)

[m5,m6,m7,m8,m9,m10,m11,m12,t1,t2,t3,t4](或按顺序每种类型至少 4 个)

[m4,m5,m6,m7,w1,w2,w3,w4,f1,f2,f3,f4](每种类型至少 4 个如果存在，但可以缺失)等等

无效:

[m4,m6,m5,m7,w1,w2,w3,w4,f1,f2,f3,f4](乱序)

[m4,m5,m6,m7,m8,w1,w2,w3,w4,f1,f2,f3](不是每种类型 4 个)

Answer 1

您可以使用带有生成器的递归:

import re, collections
data = ['m1','m2','m3','m4','m5','m6','t1','t2','t3','t4','t5','t6','w1','w2','w3','w4','w5','w6']
def combo(d, c = []):
  if len(c) == 12:
     yield c
  else:
     for i in d:
        _count1 = collections.Counter([re.findall('^[a-zA-Z]+', j)[0] for j in c])
        _count2 = collections.Counter([re.findall('^[a-zA-Z]+', j)[0] for j in c+[i]])
        if i not in c:
           if len(c) < 11 or all(b >= 4 for b in _count2.values()):
              if re.findall('^[a-zA-Z]+', i)[0] in _count1:
                 if int(re.findall('\d+$', i)[0])-1 == int(re.findall('\d+$', c[-1])[0]) and re.findall('^[a-zA-Z]+', i)[0] == re.findall('^[a-zA-Z]+', c[-1])[0]:
                    yield from combo(d, c+[i])
              else:
                 yield from combo(d, c+[i])

result = combo(data)
for _ in range(10): #first 10 results from generator
  print(next(result))

输出:

['m1', 'm2', 'm3', 'm4', 'm5', 'm6', 't1', 't2', 't3', 't4', 't5', 't6']
['m1', 'm2', 'm3', 'm4', 'm5', 'm6', 'w1', 'w2', 'w3', 'w4', 'w5', 'w6']
['m1', 'm2', 'm3', 'm4', 't1', 't2', 't3', 't4', 'w1', 'w2', 'w3', 'w4']
['m1', 'm2', 'm3', 'm4', 't1', 't2', 't3', 't4', 'w2', 'w3', 'w4', 'w5']
['m1', 'm2', 'm3', 'm4', 't1', 't2', 't3', 't4', 'w3', 'w4', 'w5', 'w6']
['m1', 'm2', 'm3', 'm4', 't2', 't3', 't4', 't5', 'w1', 'w2', 'w3', 'w4']
['m1', 'm2', 'm3', 'm4', 't2', 't3', 't4', 't5', 'w2', 'w3', 'w4', 'w5']
['m1', 'm2', 'm3', 'm4', 't2', 't3', 't4', 't5', 'w3', 'w4', 'w5', 'w6']
['m1', 'm2', 'm3', 'm4', 't3', 't4', 't5', 't6', 'w1', 'w2', 'w3', 'w4']
['m1', 'm2', 'm3', 'm4', 't3', 't4', 't5', 't6', 'w2', 'w3', 'w4', 'w5']

<小时/>

编辑:过滤掉相似的结果:

r, result = [], combo(data)
for _ in range(40):
   r.append(next(result))

new_r = [a for i, a in enumerate(r) if all(sorted(a) != sorted(k) for k in r[:i])]
print(f'{len(r)} => {len(new_r)}')

输出:

40 => 22