python - 如何查找列表 B 中有多少项形成列表 A

Question

我想找到构成列表 A 的列表 B 的最少项目。让我们假设 A=['abcdef'] 和 B=['abc','ad','adef','adef','bdf']。然后，由于索引为 0 和 2 的项目包含列表 A 的所有字母，因此答案将为 2。我使用组合来查找 B 的所有可能组合。但我不确定如何继续。似乎最优化的方法是蛮力。

A=['abcdef']
B=['abc','ad','adef','adef','bdf']

for L in range(0, len(B)+1):
    for subset in itertools.combinations(B, L):
        if subset==A:
            print(subset)

Answer 1

这是您尝试的扩展。我使用了一种相当困惑的理解来将列表展平成一个集合，这样我就可以利用简单的集合操作来检查一个是否是另一个的子集。

import itertools

A='abcdef'
B=['abc','ad','adef','adef','bdf']

set_a = set(A)
solved = False


for L in range(0, len(B)+1):
    for subset in itertools.combinations(B, L):
        s = set(item for sublist in subset for item in sublist)
        if set_a.issubset(s):
            print(f'String A can be made from {L} items of list B, specifically: {subset}')
            solved = True
            break
    if solved: break