python - 查找Python中所有解决方案列表中是否存在一组潜力的最快方法

Question

除了示例之外，我正在尝试这样做，但我认为这是最简单的解释。

假设您有一连串潜在的项目，并想找出它是否存在于已知的解决方案列表中。

    solutions = ['GAT','CAT','GCT']

你有潜力:

    potentials = [['G','T'],['T','A'],['T']]

这样您就可以确定 GAT 是唯一可以从潜力中创建的解决方案。

和

你想找到所有可能的解决方案，这样

    potentials = [['G','C','A','T'],['G','C','A','T'],['G','C','A','T']]

将返回 ['GAT','CAT','GCT'] 因为所有的解决方案都可以从潜力中得到。

我当前的解决方案只是使用 JOIN 构建所有组合，然后进行交集。

由于下一步，理想的解决方案实际上会返回一个解决方案，以便输出每个项目的可行选项，这样:

    solutions = ['GAT','CAT','GCT']
    potentials = [['G','C','A','T'],['G','C','A'],['A','T']]
    imaginaryfunction(potentials, solutions)

会返回:

     [['G','C'],['C','A'],['T']]

如果这很重要，在我的真实世界案例中有 30 个左右的“字母”，并且潜在列表中的任何给定项目最多可能是这些“字母”中的 8 个。解决方案列表大约有 2000 个三个字母的组合。在理想情况下，只有 1 种组合有效，但更常见的是有 4 种或 5 种组合，并且可能有 2000 种可能，但可能性很小。

我尝试了一些非常疯狂的事情，从连接，到从每个组合中生成一个以 30 为底的数字，这样我就可以检查该数字是否在列表中，再到将所有解决方案分解成字典看看元素是否在那里。

我的代码循环遍历了数十万次甚至数百万次，所以即使是很小的收获对我来说也能很快累积起来。

编辑/附加信息:

这在几个地方使用。我正在与一个进行药物相互作用模拟的小组合作，他们正在研究可能是附着点/结合点的链。

它也用于制作那些“个人造型师会挑选你的衣橱”每月盒子的公司。 (在那种情况下，第一个匹配集可能是 XS、S、M、L、LT、XL、XXL，第二个是红色、绿色、蓝色、黑色、白色，第三个是袖长)(他们不实际上没有人挑选盒子里的东西)

相同的代码块也在我的 NGram 分析代码中。

在约会应用程序中，相同的代码块与种族、性别、年龄、收入相同

Answer 1

由于与可能组合的理论数量(30^8 的顺序)相比，您的解决方案集非常小(2000)，我认为这样的事情可行:

solutions = get_possible_solutions()
for i, pset in enumerate(potentials):
    matching_solutions = []
    for sol in solutions:
        if sol[i] in pset:
            matching_solutions.append(sol)
    solutions = matching_solutions # Remove non-matches

此解决方案使用项目“字符串”中当前字母的潜力迭代过滤可能的解决方案。内部循环每次迭代都会变小，因此它有可能变得非常快。它至少应该比在所有可能的解决方案和输入解决方案之间进行显式交集要快得多。