python - 查找数组中创建所需结果的所有组合

Question

假设我们有包含 id、字符的数组:

[(1,'S'),(2,'P','S'),(3,'W','C'),(4,'T','C'),(5,'O','T','C'),(6,'O','S'),(7,'O'),(8,'P','O')]

是否有一种有效的方法来获取包含所有字母的所有组合: ('S','P','C','T','O','W') ,(我不知道不想要不同的订单)，并且它们的大小是 1-6？

到目前为止，我创建了数组的幂集，并迭代幂集以查找包含所有所需字母的所有组合。 它工作得很好，直到我缩放了数组(数组的大小为 500+，这意味着它的幂集的大小为 ~2^500)。

有效组合的示例是:

[(8,'P','O'),(2,'P','S'),(5,'O','T','C'),(3,'W','C')]'
(Because it has ALL of the letters in it)

Answer 1

Python 有很多函数可以在 intertools 模块中处理此类内容。

import itertools

start=[(1,'S'),(2,'P','S'),(3,'W','C'),(4,'T','C'),(5,'O','T','C'),(6,'O','S'),(7,'O'),(8,'P','O')]
good_values=set('S','P','C','T','O','W')

# Turn the tuples into sets so you can do subtraction
as_set=map(set, start)

# If the set is smaller when you pull some good_values out it is a set you care about
good_sets=[i for i in as_set if len(i - good_values) != len(i)]

# Now just ask Python for the permutations of these sets
itertools.permutations(good_sets)

如果您关心获取匹配项的所有可能顺序，请使用 itertools.permutations。如果您关心匹配的每种尺寸的每种可能的组合并且不关心顺序，请使用 itertools.combinations。如果您需要两者，请使用组合，然后对每个组合进行排列，但这在计算上会非常昂贵。