需要帮助优化组合问题

Question

我不是最好的编码员，但我正在尝试弄清楚如何计算可能组合的数量并实际生成每个组合，但有一些规则。我有两组“事物”，初级 (P) 和次级 (S)。在这种情况下，我有 P = 16 和 S = 7。因此一个有效的组合至少需要一个 P 值，但不需要 S 值才有效，因此：

P1, S1, S2 有效

P1, P2, P3 有效

P1, P2, P3, P4, S1, S2 有效

但是，

S1、S2、S3 无效。

还有 P1, S1 与 S1, P1 相同。我写了一个程序，我认为它可以解决问题，但它很糟糕并且需要两天才能运行：

import itertools

P_num = 16
S_num = 7
R = P_num + S_num

P = list(range(1,P_num+1))
S = list(range(1,S_num+1))
P = ["P" + str(suit) for suit in P]
S = ["S" + str(suit) for suit in S]
stuff = P + S

totalarray = {new_list: [] for new_list in range(1,R+1)}

for L in range(len(stuff) + 1):
    print(L)
    for subset in itertools.combinations(stuff, L):
        sublist = sorted(subset)
        if any(x in sublist for x in P):
            if sublist not in totalarray[L]:
                totalarray[L].append(sublist)

run = 0
for each in totalarray.keys():
    print(each, len(totalarray[each]))
    run += len(totalarray[each])

print(run)

我真的可以使用一些关于优化这个问题的方法的建议，我相信有更好的方法可以在没有这么多嵌套操作的情况下做到这一点。

谢谢，

我创建了这段代码，它输出了正确的结果（我认为），但它非常耗费资源：

import itertools

P_num = 16
S_num = 7
R = P_num + S_num

P = list(range(1,P_num+1))
S = list(range(1,S_num+1))
P = ["P" + str(suit) for suit in P]
S = ["S" + str(suit) for suit in S]
stuff = P + S

totalarray = {new_list: [] for new_list in range(1,R+1)}

for L in range(len(stuff) + 1):
    print(L)
    for subset in itertools.combinations(stuff, L):
        sublist = sorted(subset)
        if any(x in sublist for x in P):
            if sublist not in totalarray[L]:
                totalarray[L].append(sublist)

run = 0
for each in totalarray.keys():
    print(each, len(totalarray[each]))
    run += len(totalarray[each])

print(run)

我希望得到相同的结果，但更优化。

Answer 1

事实证明，使用一些组合数学可以大大加快你的问题。这是代码：

from math import comb
P_num = 16
S_num = 7
total = P_num + S_num

solution = 0

for length in range(total):
    for P in range(1, P_num+1):
        solution += math.comb(total-P, length)
print(solution)

此代码打印出

8 388 480

，这应该是您要查找的数字。

---

解释：

对于每个长度，我们知道至少应该有一个

P

元素。因此，对于每个可能的

P

，我们计算包含它的集合的数量。这可以使用 math.comb 来完成，这只是 n 选择 k.

---

性能：

在我的电脑上，这是

S_num=16

和

S_num=7

的新算法的速度：

106 µs ± 3.62 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Answer 2

打印到终端相对较慢。

根据你的规则，会有8,388,480个有效组合。

将有效组合写入文件比将输出发送到终端要快得多。

试试这个：

from itertools import combinations
from time import perf_counter

OUTPUT_FILE = '/Volumes/G-Drive/combos.txt'
def isvalid(c):
    for v in c:
        if v[0] == 'P':
            return True
    return False

start = perf_counter()

P_num = 16
S_num = 7

stuff = [f'P{n}' for n in range(1, P_num+1)] + [f'S{n}' for n in range(1, S_num+1)]
count = 0
with open(OUTPUT_FILE, 'w') as cfile:
    for k in range(1, len(stuff)+1):
        for combo in combinations(stuff, k):
            if isvalid(combo):
                cfile.write(f'{combo}\n')
                count += 1

print(f'Count={count:,}, Duration={perf_counter()-start:.2f}s')

输出：

Count=8,388,480, Duration=11.07s