根据某些约束来计算组合总数的算法

Question

我有一些应该组合的字母。 该字母应在相应的地方合并，并选择省略一些字母。 例如，

对于A，我有A1，A2，A3。

对于B，我有B1，B2。

对于C，我有C1，C2，C3，C4。

对于D，我有D1，D2。

组合的一个例子是A1，B2，C1，D2。另一个可能的组合是_，b2，c1，d2（省略字母A）。

没有任何约束，总组合将为（3+1）（2+1）（4+1）（2+1）= 180组合。

但是，我想根据一些约束来计算总组合。 例如，基于[A1不能与B2一起出现]的约束，并且[A2不能与C4一起出现]总组合小于180。

我知道这可以通过包容性排斥原则来完成，但是这是非常困难的为了编程包含，排除计算。还有其他算法，而不是包容性排斥原则和蛮力吗？

非常感谢！！

Answer 1

我相信您高估了编码包容性排斥的努力。

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