如何生成n个变量的所有布尔逻辑组合并实现通用分组？

问题需求 #

已有代码可生成n个元素的无括号布尔逻辑序列（例如3个元素A/B/C会生成[A,AND,B,OR,C]这类结构），现在需要为这些序列添加所有可能的逻辑分组（比如对A AND B OR C生成(A AND B) OR C和A AND (B OR C)），并将逻辑泛化到任意n个元素的列表。

解决方案 #

核心思路 #

对于n个元素的布尔表达式，所有逻辑分组本质对应不同的运算符优先级，可通过递归枚举所有二叉树结构实现：

• 单个元素时，直接返回元素本身
• 多元素表达式，遍历每个运算符位置，将表达式拆分为左右两部分，递归生成左右的所有分组，再用当前运算符连接并添加括号

代码实现 #

import itertools
from itertools import chain, zip_longest

BOOL = ['AND', 'OR']

def get_macro_comb(keys):
    """生成固定元素顺序下的所有无括号布尔表达式序列"""
    needed_bool = len(keys) - 1
    operator_combs = itertools.product(BOOL, repeat=needed_bool)
    all_aud = []
    for ops in operator_combs:
        expr = list(chain(*zip_longest(keys, ops)))
        expr = [x for x in expr if x is not None]
        all_aud.append(expr)
    return all_aud

def generate_all_groupings(expr):
    """递归生成单个无括号表达式的所有逻辑分组形式"""
    if len(expr) == 1:
        return [expr[0]]
    
    groupings = []
    # 遍历所有运算符的位置（索引为奇数）
    for i in range(1, len(expr), 2):
        op = expr[i]
        left_expr = expr[:i]
        right_expr = expr[i+1:]
        # 递归生成左右部分的所有分组
        left_groups = generate_all_groupings(left_expr)
        right_groups = generate_all_groupings(right_expr)
        # 组合所有可能的左右分组
        for left in left_groups:
            for right in right_groups:
                groupings.append(f"({left} {op} {right})")
    return groupings

def get_all_boolean_expressions(elements):
    """生成所有元素排列、运算符组合、逻辑分组的布尔表达式"""
    # 生成元素的所有排列（若不需要考虑顺序可注释此部分，直接传入固定列表）
    element_permutations = itertools.permutations(elements)
    all_exprs = []
    for perm in element_permutations:
        for comb in get_macro_comb(perm):
            groupings = generate_all_groupings(comb)
            all_exprs.extend(set(groupings))  # 去重语法重复的表达式
    # 最终去重所有表达式
    return list(set(all_exprs))

# 测试示例
if __name__ == "__main__":
    elements = ['A', 'B', 'C']
    all_exprs = get_all_boolean_expressions(elements)
    for expr in sorted(all_exprs):
        print(expr)

代码说明 #

1. get_macro_comb：生成固定元素顺序下，所有运算符组合的无括号表达式序列
2. generate_all_groupings：递归处理单个无括号表达式，枚举所有可能的逻辑分组
3. get_all_boolean_expressions：整合元素排列（可选）、运算符组合、逻辑分组，生成所有可能的布尔表达式
4. 若不需要考虑元素顺序，可移除element_permutations相关代码，直接传入固定元素列表

内容的提问来源于stack exchange，提问作者laila