Python实现XOR线性方程组求解器 基于n行n+1列增广矩阵返回未知量解列表

核心原理 #

XOR运算等价于**GF(2)域（仅包含0、1元素，加法为异或、乘法为与）**上的加法运算，因此XOR线性方程组求解本质是对增广矩阵做模2高斯消元。

实现步骤 #

1. 基于输入的n行n+1列增广矩阵，构造可读的异或方程组（匹配列与变量的对应关系）
2. 对增广矩阵执行模2高斯消元，判断是否存在无解情况
3. 提取解后按要求的x1、x2…xn顺序调整返回

完整代码实现 #

def build_xor_equations(augmented_matrix):
    """
    基于增广矩阵构造异或方程组
    参数：n行n+1列的增广矩阵，前n列按xn、x(n-1)...x1的顺序存储系数，最后1列为常数项
    返回：方程组字符串列表
    """
    n = len(augmented_matrix)
    equations = []
    for row in augmented_matrix:
        terms = []
        for col_idx in range(n):
            if row[col_idx] == 1:
                # 第col_idx列对应变量为x(n - col_idx)
                terms.append(f"x{n - col_idx}")
        left = "+".join(terms) if terms else "0"
        right = str(row[-1])
        equations.append(f"{left}={right}")
    return equations
def solve_xor_system(augmented_matrix):
    """
    求解XOR线性方程组
    参数：n行n+1列的增广矩阵，元素仅为0/1，前n列按xn、x(n-1)...x1的顺序存储系数
    返回：按[x1, x2, ..., xn]顺序排列的解列表
    异常：方程组无解时抛出ValueError
    """
    n = len(augmented_matrix)
    # 校验输入合法性
    for row in augmented_matrix:
        if len(row) != n + 1:
            raise ValueError(f"每行需包含{n+1}个元素")
        for num in row:
            if num not in (0, 1):
                raise ValueError("矩阵元素仅能为0或1")
    # 拷贝矩阵避免修改原输入
    mat = [row.copy() for row in augmented_matrix]
    pivot_cols = []
    current_row = 0
    # 遍历所有系数列做消元
    for col in range(n):
        # 找当前列从current_row往下的第一个非0主元
        pivot_row = None
        for i in range(current_row, n):
            if mat[i][col] == 1:
                pivot_row = i
                break
        if pivot_row is None:
            # 当前列无主元，对应自由变量，跳过
            continue
        # 交换当前行与主元行
        mat[current_row], mat[pivot_row] = mat[pivot_row], mat[current_row]
        # 消去其他所有行的当前列
        for i in range(n):
            if i != current_row and mat[i][col] == 1:
                # 行异或（模2加法）
                for j in range(col, n + 1):
                    mat[i][j] ^= mat[current_row][j]
        pivot_cols.append(col)
        current_row += 1
    # 检查是否存在矛盾行（0=1）
    for i in range(current_row, n):
        if mat[i][-1] == 1:
            raise ValueError("该XOR线性方程组无解")
    # 提取解：自由变量默认取0
    solution = [0] * n
    for i in range(len(pivot_cols)):
        col = pivot_cols[i]
        solution[col] = mat[i][-1]
    # 解当前顺序为[xn, x(n-1)...x1]，反转后得到要求的[x1, x2...xn]顺序
    return solution[::-1]

示例测试 #

用题目给出的增广矩阵测试：

# 题目示例的增广矩阵
aug_matrix = [
    [1, 1, 0, 1, 0],
    [1, 0, 1, 0, 1],
    [0, 1, 0, 1, 1],
    [1, 0, 1, 1, 0]
]
# 构造方程组
equations = build_xor_equations(aug_matrix)
print("构造的方程组：")
for eq in equations:
    print(eq)
# 求解
sol = solve_xor_system(aug_matrix)
print("求解结果（x1、x2、x3、x4顺序）：", sol)

运行输出 #

构造的方程组：
x4+x3+x1=0
x4+x2=1
x3+x1=1
x4+x2+x1=0
求解结果（x1、x2、x3、x4顺序）： [1, 0, 0, 1]

注意事项 #

• 若方程组存在自由变量（无穷多解），当前实现默认将自由变量取为0，返回其中一组特解
• 若需要枚举所有解，可在基础解的基础上对自由变量的所有可能组合（0/1）做线性叠加即可

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