使用 Python 求解二元方程组的多解问题

from itertools import product

# 定义方程组
def check_solution(x, y, z, v, w):
    return (
        (x ^ z == 1) and
        (x ^ y ^ z ^ v ^ w == 1) and
        (v ^ w == 1) and
        (y == 1)
    )

# 遍历所有可能的变量组合
for x, y, z, v, w in product([0, 1], repeat=5):
    if check_solution(x, y, z, v, w):
        print(x, y, z, v, w)

from itertools import product

xp, yp, zp, vp, wp = (0, 1, 1, 0, 1)

yh = 0
for xh, vh in product(range(2), repeat=2):
    zh, wh = xh, vh
    x, y, z, v, w = (xp ^ xh, yp ^ yh, zp ^ zh, vp ^ vh, wp ^ wh)

    assert x ^ z == 1
    assert x ^ y ^ z ^ v ^ w == 1
    assert v ^ w == 1
    assert y == 1
    print(x, y, z, v, w)

pip install galois numpy sympy

from galois import GF2
from numpy import hstack, zeros
from numpy.linalg import solve, LinAlgError
from itertools import combinations

from sympy import Matrix, symbols
from sympy import solve_linear_system

A = GF2((
    (1, 0, 1, 0, 0,),
    (1, 1, 1, 1, 1),
    (0, 0, 0, 1, 1),
    (0, 1, 0, 0, 0),
))
b = GF2(((1, 1, 1, 1),)).T
Ab = hstack((A, b))

# 高斯消元
Ab_reduced = Ab.row_space()
A_reduced = Ab_reduced[:, :-1]
b_reduced = Ab_reduced[:, -1:]

# 寻找特解
n_eqs, n_vars = A_reduced.shape

for idx in combinations(range(n_vars), r=n_eqs):
    try:
        sol = solve(A_reduced[:,idx], b_reduced)
        break
    except LinAlgError:
        pass

particular_solution = n_vars * [0]
for j, i in enumerate(idx):
    particular_solution[i] = int(b_reduced[j])
particular_solution = GF2(particular_solution)

# 求解齐次方程的通解
zero_col = GF2((zeros(n_eqs, dtype=int), )).T
x, y, z, v, w = symbols("x y z v w")
A_homogenous = hstack((A_reduced, zero_col))
solve_linear_system(Matrix(A_homogenous), x, y, z, v, w)