在Python中用多个解求解二元方程

获得所有解的方法与获得任何线性方程组的方法相同:

• 找到一个特定的解决方案(你已经有0, 1, 1, 0, 1个了)
• 然后求出齐次方程的通解.

然后，您可以将齐次方程的任何解添加到特定解.

在您的例子中:方程式系统(写为矩阵)如下所示:

[1 0 1 0 0]
[1 1 1 1 1]
[0 0 0 1 1]
[0 1 0 0 0]

如果对其应用高斯消go 法，则会得到:

[1 0 1 0 0]
[0 1 0 0 0]
[0 0 0 1 1]
[0 0 0 0 0]

这意味着现在要与变量的向量相乘.因此，齐次方程的通解公式可以读出下面必须满足的条件:

yh = 0   # from [0 1 0 0 0]
zh = xh  # from [1 0 1 0 0]
wh = vh  # from [0 0 0 1 1]

你可以 Select xh和vh

把它们中的任何一个加到特定的解上，你就得到了所有的解:

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)

要实现以下目标:

0 1 1 0 1
0 1 1 1 0
1 1 0 0 1
1 1 0 1 0

没有不必要的循环.变量的所有设置都是方程式的解.

Update:个

(免责声明:所有这些都没有经过真正的测试...)

为了得到方程的梯形形式，您可以安装galois和sympy，并按如下方式使用它们:

为此，您需要:

pip install galois numpy sympy

然后:

from galois import GF2
from numpy import  hstack, dot
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))
# GF([[1, 0, 1, 0, 0, 1],
#     [1, 1, 1, 1, 1, 1],
#     [0, 0, 0, 1, 1, 1],
#     [0, 1, 0, 0, 0, 1]], order=2)

高斯消go :

Ab_reduced = Ab.row_space()
# GF([[1, 0, 1, 0, 0, 1],
#     [0, 1, 0, 0, 0, 1],
#     [0, 0, 0, 1, 1, 1]], order=2)

A_reduced = Ab_reduced[:, :-1]
# GF([[1, 0, 1, 0, 0],
#     [0, 1, 0, 0, 0],
#     [0, 0, 0, 1, 1]], order=2)

b_reduced = Ab_reduced[:, -1:]
# GF([[1],
#     [1],
#     [1]], order=2)

我在NumPy中找不到直接找到特定解决方案的函数. 这样的函数可能存在(？).

我数了变量的个数和方程的个数，设置了n_vars-n_eqs个变量 设置为零，并希望使用solve为其余变量找到解决方案:

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)
# GF([1, 1, 0, 1, 0], order=2)

然后，对于一般的解决方案，我使用了sympy(它不知道GF(2)，可能并不总是像预期的那样工作？)

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)
# {x: -z, y: 0, v: -w}

-z表明，sympy不知道GF(2).但在这种情况下，它仍然有效.