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']，因为所有的解决方案都可以从电势中得到。你知道吗

我当前的解决方案只是使用连接构建所有组合，然后进行交集。你知道吗

因为下一步，一个理想的解决方案实际上会返回一个解决方案，从而输出每个项目的可行选项，从而：

    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个三字母组合。在一个理想的世界里，只有一个组合是有效的，但更典型的是有4个或5个组合，这是可能的，但极不可能让所有的2000个都成为可能。你知道吗

我做过一些非常疯狂的实验，从连接到从每个组合中提取一个以30为基数的数字，这样我就可以检查这个数字是否在列表中，再到将所有的解决方案分解到一个字典字典中，看看这些项是否在那里。你知道吗

我的代码循环了这10万次，如果不是数百万次的话，所以即使是很小的收益，对我来说也很快累积起来。你知道吗

编辑/附加信息：

这在很多地方都有使用。我正在和一个研究药物相互作用模拟的小组合作，他们正在研究可能是附着点/结合点的链。你知道吗

它也被用于一家公司，做那些“个人设计师会选择你的衣柜”每月盒。（在这种情况下，第一组可能是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

此解决方案使用项“string”中当前字母的势迭代地过滤可能的解决方案。 每次迭代，内部循环都会变小，所以这可能会非常快。 它至少应该比在所有可能的解和输入解之间进行显式交集快得多。你知道吗