具有高级过滤功能的2 ^ n Itertools组合

2018-07-02 15:33:40

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

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

这样的输出就像元组列表，在这种情况下每个元组的长度都是4。

从这里，我想要做的是强制执行2个参数 - 1）排除包含某些对的任何组合/元组 - 例如V和M，或者Q和K. 2）强制每个元组只包含1个实例一封信。我相信itertools已经在做＃2。

剩下的只是那些不包含任何这些预定义的“假”对的元组。因此，如果我排除了包含V和M的组，那么该组('V','M','Q','D')将是无效的，但是('V','R','Q','D')将是有效的。

我做这件事最好的办法是什么？

你可以定义一个验证函数并用它来过滤

>>> 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的想法结合使用

>>> 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将任意数量的不需要的排除组合作为参数，然后生成一个执行检查并返回的函数; 您可以将结果保留在变量中或直接使用它

我会过滤一组：

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中进行滚动也可能会慢一点吧，你有一个大的数据集

您可以使用带有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'）并将其扔掉，依此类推。在这种情况下生成的组合的数量不是问题。对于较大的组合，您可能想要使用自定义递归算法提前丢弃无效的部分结果。

链接地址: http://www.djcxy.com/p/90997.html

上一篇: 2^n Itertools combinations with advanced filtering

下一篇: Violation of type safety in C++ with function declaration of other type?