I have some set of letters that should be combined. The letter should be combined in corresponding places with a choice of omitting some letter. For example,
For A, I have A1, A2, A3.
For B, I have B1, B2.
For C, I have C1, C2, C3, C4.
For D, I have D1, D2.
One example of the combination is A1,B2,C1,D2. Another possible combination is _,B2,C1,D2 (omitting letter A).
Without any constraints, the total combinations would be (3+1)(2+1)(4+1)(2+1) = 180 combinations.
However, I would like to count the total combinations based on some constraints. For example, on the constraint that [A1 cannot occur together with B2] and [A2 cannot occur together with C4] the total combination would be less than 180.
I know this could be done with inclusion-exclusion principle, but it is quite difficult to program the inclusion, exclusion calculation. Is there any other algorithms rather than the inclusion-exclusion principle and brute force?
Thank you very much!!
I believe that you are overestimating the effort of coding inclusion-exclusion.
class LetterRule:
def __init__ (self, letter, positions):
self.letter = letter
if isinstance(positions, list):
self.positions = positions
else:
self.positions = [positions]
def count_matching_combinations (letter_allowed):
answer = 1
for allowed in letter_allowed.values():
answer *= len(allowed)
return answer
def matching_rule_allowed (letter_allowed, rule):
# Make a copy
letter_allowed = letter_allowed.copy()
for letter_rule in rule:
allowed = letter_allowed[letter_rule.letter]
allowed = [x for x in allowed if x in letter_rule.positions]
if 0 == len(allowed):
return None
letter_allowed[letter_rule.letter] = allowed
return letter_allowed
# This is the inclusion-exclusion logic.
def matching_combination_counts (letter_allowed, rules, i=None, sign=1):
if i is None:
yield(count_matching_combinations(letter_allowed))
for i in range(len(rules)):
yield from matching_combination_counts(
letter_allowed, rules, i, -1)
else:
letter_allowed = matching_rule_allowed(letter_allowed, rules[i])
if letter_allowed is not None:
yield sign * count_matching_combinations(letter_allowed)
for j in range(i+1, len(rules)):
yield from matching_combination_counts(
letter_allowed, rules, j, sign * -1)
def count_combinations (letter_allowed, rules=None):
if rules is None:
rules = []
return sum(matching_combination_counts(letter_allowed, rules))
letter_allowed = {
'A': [0, 1, 2, 3],
'B': [0, 1, 2],
'C': [0, 1, 2, 3, 4],
'D': [0, 1, 2],
}
rules = [
[LetterRule('A', 1), LetterRule('B', 2)],
[LetterRule('A', 2), LetterRule('C', 4)],
]
print(count_combinations(letter_allowed, rules))