生成满足 Python 中多个条件的排列？

Question

我正在尝试生成满足各种子标准的所有可能排列的列表。我不能采用蛮力方法，因为内存使用会成为一个问题。理想情况下，我会使用 itertools 和生成器的某种组合来管理生成的排列数。

Objective

生成 20 个项目的排列，这些项目被分成四个子集，每组 5 个项目。

约束条件

每一项可以等于 4、5 或 6
每个排列集的总和必须为 100
每个子集的总和必须在 20 到 30 之间

例子

66655 / 44455 / 46465 / 56644 是允许的，因为子组件总和在 20 到 30 (28 / 22 / 25 / 25) 之间，总和等于 100。

不幸的是，我真的不知道从哪里开始！任何指导将不胜感激。

Answer 1

这将产生数亿个有效的解决方案。将它们存储在列表中需要 3GB 的内存，但您可以在不存储它们的情况下生成解决方案。

以下是制作它们的方法（在此示例中我只计算它们）：

在子集总数 (20,21,22,...30) 和可以产生它们的数字 4,5,6 的排列之间创建映射

from itertools import permutations,product,chain

subSums = dict()
for combo in combinations([4,5,6]*5,5):
    if sum(combo) not in range(20,31): continue
    subSums.setdefault(sum(combo),set()).add(combo)
            
print(sum(map(len,subSums.values()))) # 243
for subtotal,combos in sorted(subSums.items()):
    print(subtotal,len(combos),":",[*combos][:3],"..."*(len(combos)>3))

20 1 : [(4, 4, 4, 4, 4)] 
21 5 : [(4, 5, 4, 4, 4), (5, 4, 4, 4, 4), (4, 4, 5, 4, 4)] ...
22 15 : [(4, 5, 4, 5, 4), (4, 4, 4, 6, 4), (4, 4, 5, 5, 4)] ...
23 30 : [(4, 4, 5, 6, 4), (4, 4, 6, 5, 4), (6, 5, 4, 4, 4)] ...
24 45 : [(5, 4, 6, 4, 5), (5, 4, 4, 6, 5), (5, 5, 4, 4, 6)] ...
25 51 : [(6, 4, 5, 6, 4), (6, 4, 6, 5, 4), (6, 5, 5, 5, 4)] ...
26 45 : [(5, 5, 5, 5, 6), (5, 4, 5, 6, 6), (5, 4, 6, 5, 6)] ...
27 30 : [(6, 5, 6, 5, 5), (6, 5, 5, 6, 5), (6, 6, 5, 6, 4)] ...
28 15 : [(4, 6, 6, 6, 6), (5, 5, 6, 6, 6), (6, 6, 4, 6, 6)] ...
29 5 : [(5, 6, 6, 6, 6), (6, 6, 6, 6, 5), (6, 5, 6, 6, 6)] ...
30 1 : [(6, 6, 6, 6, 6)]

生成 20、21、22、...30 中的 4 个小计的排列，总计为 100

groupSums = set()
for combo in combinations([*range(20,31)]*4,4):
    if sum(combo) != 100: continue
    groupSums.add(combo)
    
print(len(groupSums)) # 891
for group in sorted(groupSums): print(group)

(20, 20, 30, 30)
(20, 21, 29, 30)
(20, 21, 30, 29)
(20, 22, 28, 30)
(20, 22, 29, 29)
(20, 22, 30, 28)
(20, 23, 27, 30)
(20, 23, 28, 29)
(20, 23, 29, 28)
(20, 23, 30, 27)
...

对于4个小计的每个排列，结合可以产生每个小计的4,5,6的排列

solutions      = [] # not going to actually fill this
totalSolutions = 0
for g1,g2,g3,g4 in groupSums:
    groupSolutions  = len(subSums[g1])
    groupSolutions *= len(subSums[g2])
    groupSolutions *= len(subSums[g3])
    groupSolutions *= len(subSums[g4])
    totalSolutions += groupSolutions

    # actual solutions would be
    # for solution in product(subSums[g1],subSums[g2],subSums[g3],subSums[g4]):
    #     solutions.append([*chain.from_iterable(solution)])
    
print(totalSolutions) # 377,379,369 solutions

如果您只需要生成解决方案（而不是将它们存储在列表中），您可以制作一个生成器函数：

def genGroups():
    for g1,g2,g3,g4 in groupSums:
        yield from product(subSums[g1],subSums[g2],subSums[g3],subSums[g4])

for solution in genGroups(): 
    g1,g2,g3,g4 = map(sum,solution)
    print((g1,g2,g3,g4),":",*chain.from_iterable(solution))

(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 4 4 5 6 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 4 4 6 5 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 6 5 4 4 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 5 6 4 4 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 5 5 4 5 4
...
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 4 5 6
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 5 4 6
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 6 5 5 4
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 6 4 5
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 4 6 5
...
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 6 6 5 5
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 5 6 6 5
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 5 6 6 5 6
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 5 6 5 6 6
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 6 6 6 4
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 5 6 5 6

在我的笔记本电脑上生成所有解决方案而不存储它们需要 27 秒。

sum(1 for _ in genGroups()) # 377379369 in 27.49 seconds

生成器可用于填充列表（而不是上面的 for 循环）：

L = list(genGroups())

生成满足 Python 中多个条件的排列？

Generating permutations that meet multiple criteria in Python?

python

combinations

iterator

generator

permutation