查找 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']]

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

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

因为下一步，一个理想的解决方案实际上 return 一个解决方案，使得每个项目的可行选项输出如下：

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

会 return:

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

如果这很重要，在我的真实世界案例中有 30 个 "letters"，并且潜在列表中的任何给定项目最多可能是其中的 8 个 "letters"。解决方案列表大约有 2000 个三个字母的组合。在一个理想的世界中，只有 1 种组合有效，但更常见的是有 4 或 5 种组合，并且有可能但极不可能拥有所有 2000 种可能。

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

我的代码循环了这 100 甚至数百万次，所以即使是很小的收获对我来说也很快。

Edit/Additional 信息：

这在几个地方都有用。我正在与一个进行药物相互作用模拟的小组合作，他们正在研究可能 attachment/bonding 点的链。

它也用于制作那些 "Personal Stylist will pick your wardrobe" 每月盒子的公司。（在那种情况下，第一个匹配集可能是 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" 中当前字母的潜力迭代过滤可能的解决方案。内部循环每次迭代都会变小，因此它有可能变得非常快。它至少应该比在所有可能的解决方案和输入解决方案之间进行显式交集要快得多。

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

Fastest way to find if a Group of potentials exists in a list of all solutions in Python

python

union

permutation

itertools