如何生成带约束的欠定0-1线性方程组的所有解？

核心思路 #

由于所有方程的系数都是1，问题本质是变量子集的和约束。我们可以先通过SymPy求解实数域内的通解，再将通解映射为0-1整数解，避免暴力枚举所有可能的组合。

步骤1：动态构建方程组并求解通解 #

根据运行时获取的变量名列表创建符号变量，构建方程组后用linsolve求解通解——欠定系统的通解会包含自由变量，后续只需遍历这些自由变量的0/1取值即可推导所有有效解。

from sympy import symbols, Eq, linsolve

# 运行时动态获取的变量名列表（示例）
var_names = ["a1", "a2", "a3"]
sym_vars = symbols(var_names)

# 构建示例方程组（可根据实际需求动态生成）
equations = [
    Eq(sym_vars[0] + sym_vars[1], 1),
    Eq(sym_vars[0] + sym_vars[2], 1)
]

# 求解线性方程组的通解
general_solution = linsolve(equations, sym_vars)

步骤2：将通解转化为0-1解 #

遍历自由变量的所有0/1组合，代入通解计算其他变量的值，过滤掉非0/1的无效结果，最终得到所有合法解。

from itertools import product

def get_binary_solutions(general_sol, variables):
    valid_solutions = []
    if not general_sol:
        return valid_solutions
    
    # 提取通解表达式和所有自由变量
    sol_expressions = list(general_sol.args[0])
    free_vars = list(set().union(*[expr.free_symbols for expr in sol_expressions]))
    
    # 遍历自由变量的所有0/1组合
    for free_vals in product([0, 1], repeat=len(free_vars)):
        substitution = dict(zip(free_vars, free_vals))
        # 计算所有变量的取值
        current_vals = [expr.subs(substitution) for expr in sol_expressions]
        # 验证是否全为0或1
        if all(val in (0, 1) for val in current_vals):
            valid_solutions.append(list(current_vals))
    return valid_solutions

# 调用函数获取所有0-1解
binary_solutions = get_binary_solutions(general_solution, sym_vars)
print(binary_solutions)
# 输出：[[0, 1, 1], [1, 0, 0]]

关键优化 #

1. 提前过滤矛盾约束：若方程形如sum(变量) = k，先判断k是否在0到变量个数之间，直接排除无解的情况
2. 合并等价方程：移除重复的约束方程，减少计算量
3. 自由变量枚举优势：仅需枚举2^f次（f为自由变量个数），远小于暴力法的2^n次（n为总变量数），约束越多效率提升越明显

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