2^n个迭代工具组合和高级过滤

Question

我知道可以使用itertools来生成组合，并定义组合的大小，如下所示：

import itertools
print list(itertools.combinations(['V','M','T','O','Q','K','D','R'], 4))

这将产生一个元组列表，每个元组的长度为4。 接下来，我想实现两个参数：1）排除包含特定对（例如V和M或Q和K）的任何组合/元组。2）强制每个元组只包含一个字母实例。我相信itertools已经实现了#2。 剩下的应该只有那些不包含这些预定“错误”对的元组组。因此，如果我排除了包含V和M的一组，则('V','M','Q','D')组将无效，但('V','R','Q','D')组将有效。 最好的方法是什么？

- DNburtonguster

---

你只需要手动筛选，就可以滚动自己的实现。 - Padraic Cunningham

Answer 1

你可以定义一个验证函数，并使用该函数进行过滤。

>>> import itertools
>>> def is_valid(data):
        if 'V' in data and 'M' in data:
            return False
        if 'Q' in data and 'K' in data:
            return False
        return True

>>> filter(is_valid,itertools.combinations('VMTOQKDR', 4))
[('V', 'T', 'O', 'Q'), ('V', 'T', 'O', 'K'), ('V', 'T', 'O', 'D'), ('V', 'T', 'O', 'R'), ('V', 'T', 'Q', 'D'), ('V', 'T', 'Q', 'R'), ('V', 'T', 'K', 'D'), ('V', 'T', 'K', 'R'), ('V', 'T', 'D', 'R'), ('V', 'O', 'Q', 'D'), ('V', 'O', 'Q', 'R'), ('V', 'O', 'K', 'D'), ('V', 'O', 'K', 'R'), ('V', 'O', 'D', 'R'), ('V', 'Q', 'D', 'R'), ('V', 'K', 'D', 'R'), ('M', 'T', 'O', 'Q'), ('M', 'T', 'O', 'K'), ('M', 'T', 'O', 'D'), ('M', 'T', 'O', 'R'), ('M', 'T', 'Q', 'D'), ('M', 'T', 'Q', 'R'), ('M', 'T', 'K', 'D'), ('M', 'T', 'K', 'R'), ('M', 'T', 'D', 'R'), ('M', 'O', 'Q', 'D'), ('M', 'O', 'Q', 'R'), ('M', 'O', 'K', 'D'), ('M', 'O', 'K', 'R'), ('M', 'O', 'D', 'R'), ('M', 'Q', 'D', 'R'), ('M', 'K', 'D', 'R'), ('T', 'O', 'Q', 'D'), ('T', 'O', 'Q', 'R'), ('T', 'O', 'K', 'D'), ('T', 'O', 'K', 'R'), ('T', 'O', 'D', 'R'), ('T', 'Q', 'D', 'R'), ('T', 'K', 'D', 'R'), ('O', 'Q', 'D', 'R'), ('O', 'K', 'D', 'R')]
>>> 

编辑

为了使其更加灵活，您可以创建一个生成验证函数的函数，并将其与@PadraicCunningham使用set的想法相结合。

>>> import itertools
>>> def make_validator(*checks):
        checker=[set(x) for x in checks]
        def validator(data):
            return not any( st.issubset(data) for st in checker)
        return validator

>>> is_valid = make_validator("VM","QK")
>>> filter(is_valid, itertools.combinations('VMTOQKDR', 4))
[('V', 'T', 'O', 'Q'), ('V', 'T', 'O', 'K'), ('V', 'T', 'O', 'D'), ('V', 'T', 'O', 'R'), ('V', 'T', 'Q', 'D'), ('V', 'T', 'Q', 'R'), ('V', 'T', 'K', 'D'), ('V', 'T', 'K', 'R'), ('V', 'T', 'D', 'R'), ('V', 'O', 'Q', 'D'), ('V', 'O', 'Q', 'R'), ('V', 'O', 'K', 'D'), ('V', 'O', 'K', 'R'), ('V', 'O', 'D', 'R'), ('V', 'Q', 'D', 'R'), ('V', 'K', 'D', 'R'), ('M', 'T', 'O', 'Q'), ('M', 'T', 'O', 'K'), ('M', 'T', 'O', 'D'), ('M', 'T', 'O', 'R'), ('M', 'T', 'Q', 'D'), ('M', 'T', 'Q', 'R'), ('M', 'T', 'K', 'D'), ('M', 'T', 'K', 'R'), ('M', 'T', 'D', 'R'), ('M', 'O', 'Q', 'D'), ('M', 'O', 'Q', 'R'), ('M', 'O', 'K', 'D'), ('M', 'O', 'K', 'R'), ('M', 'O', 'D', 'R'), ('M', 'Q', 'D', 'R'), ('M', 'K', 'D', 'R'), ('T', 'O', 'Q', 'D'), ('T', 'O', 'Q', 'R'), ('T', 'O', 'K', 'D'), ('T', 'O', 'K', 'R'), ('T', 'O', 'D', 'R'), ('T', 'Q', 'D', 'R'), ('T', 'K', 'D', 'R'), ('O', 'Q', 'D', 'R'), ('O', 'K', 'D', 'R')]
>>> filter(make_validator("VM","QK",'MT',"DR"), itertools.combinations('VMTOQKDR', 4))
[('V', 'T', 'O', 'Q'), ('V', 'T', 'O', 'K'), ('V', 'T', 'O', 'D'), ('V', 'T', 'O', 'R'), ('V', 'T', 'Q', 'D'), ('V', 'T', 'Q', 'R'), ('V', 'T', 'K', 'D'), ('V', 'T', 'K', 'R'), ('V', 'O', 'Q', 'D'), ('V', 'O', 'Q', 'R'), ('V', 'O', 'K', 'D'), ('V', 'O', 'K', 'R'), ('M', 'O', 'Q', 'D'), ('M', 'O', 'Q', 'R'), ('M', 'O', 'K', 'D'), ('M', 'O', 'K', 'R'), ('T', 'O', 'Q', 'D'), ('T', 'O', 'Q', 'R'), ('T', 'O', 'K', 'D'), ('T', 'O', 'K', 'R')]
>>> 

make_validator 接受任意数量的排除组合作为参数，并创建一个检查并返回结果的函数；您可以将结果保存在变量中或直接使用它。

- Copperfield

---

这正是我所寻找的，无论是灵活性还是速度方面。在看到这个之前，我不知道itertools也可以拆分字符字符串。 - DNburtonguster

字符串就像是字符列表，因此将字符串或字面字符列表传递给任何处理可迭代对象的函数都是相同的。 - Copperfield

为了增加灵活性，您可以像我的新添加一样创建一个验证器工厂。 - Copperfield

Answer 2

我会用一个集合进行过滤：

import itertools
c = itertools.combinations(['V','M','T','O','Q','K','D','R'], 4)

st = {"V","M"}

print([co for co in c if not st.issubset(co)])

如果您想要筛选出两个：

st1 = {"V","M"}
st2 = {"Q","K"}

print([co for co in c if not st1.issubset(co) and not st2.issubset(co)])

如果您有两个以上，最好使用any:

sts = [{"V","M"},{"V","R"},{"T","O"}]

print([co for co in c if not any(st.issubset(co) for st in sts)])

如果您自己编写组合逻辑，那么即使您使用纯Python编写，也无法避免创建所有组合并进行过滤，除非您拥有大型数据集，否则速度可能会更慢。

- Padraic Cunningham

Answer 3

你可以使用带有if条件语句的列表推导式：

>>> [x for x in itertools.combinations('VMTOQKDR', 4) 
       if not (('V' in x and 'M' in x) or ('Q' in x and 'K' in x))]
[('V', 'T', 'O', 'Q'),
 ('V', 'T', 'O', 'K'),
 ... 37 more ...
 ('O', 'Q', 'D', 'R'),
 ('O', 'K', 'D', 'R')]

请注意，这仍将通过所有组合，并且只会“丢弃”无效的组合。例如，如果前两个元素是('V','M')，它将继续生成`('V','M','O','R')`并将其丢弃，依此类推。对于在此情况下生成的组合数量，这不是问题。对于更大的组合，您可能希望使用自定义递归算法更早地丢弃无效的部分结果。

- tobias_k