Algorithm for Counting Total Number of Combinations based on some constraints

user_18158357 0
Viewed 41

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!!

combinations counting algorithm
1 Answers

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))
user_5854110
Related