2 ^ n Itertools Advanced Filter Combinations

Question

I know that I can use itertools to deflate combinations and determine the size of a group of combinations, for example:

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

The result of this will look like a list of tuples, each of which has a length of 4 in this case.

From here I have to perform 2 parameters - 1) exclude any combinations / tuples that contain certain pairs - for example, V and M, or Q and K. 2) Force each tuple to contain only 1 copy of the letter. I believe itertools is already doing # 2.

What should remain is only those groups of tuples that do not contain any of these predetermined “false” pairs. Therefore, if I exclude the group containing V and M, the group ('V','M','Q','D') will be invalid, but ('V','R','Q','D') will be valid.

What is the best way for me to do this?

Answer 1

you can define a validation function and filter using this

 >>> 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')] >>> 

EDIT

To make it even more flexible, you can make a function that performs validation functions, and mix it with @PadraicCunningham's idea of ​​using 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')] >>> 

the make_validator takes as arguments any number of exclusive combinations that you don’t want, and create a function that performs the check and returns it; you can save the result in a variable or use it directly

Answer 2

I would filter using a set:

 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)]) 

If you want to filter by two:

 st1 = {"V","M"} st2 = {"Q","K"} print([co for co in c if not st1.issubset(co) and not st2.issubset(co)]) 

If you have more than two, it would be better to use any :

 sts = [{"V","M"},{"V","R"},{"T","O"}] print([co for co in c if not any(st.issubset(co) for st in sts)]) 

You abandon your own combining logic, you cannot avoid creating all combinations and filtering, even if you do it yourself, in pure python it will probably be slower than you had a large dataset

Answer 3

You can use list comprehension with the if condition:

 >>> [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')] 

Note that this will still go through all the combinations and just “throw away” the invalid ones. For example, if the first two elements are ('V','M') , it will continue to generate `('V', 'M', 'O', 'R') and throw it away, etc. For the number of combinations generated in this case, this is not a problem. For larger combinations, you may need to produce invalid partial results earlier using a custom recursive algorithm.