You have given equations where the variables can take on the values 0 and 1 (false = 0 true = 1) and the result of the equation will always be 1:
X Y Z V W
1, 0, 1, 0, 0
1, 1, 1, 1, 1
0, 0, 0, 1, 1
0, 1, 0, 0, 0
You can rewrite it as: (“+” = XOR)
X + Z = 1
X + Y + Z + V + W = 1
V + W = 1
Y = 1
This example should have 4 solutions:
X Y Z V W
1)0, 1, 1, 0, 1
2)0, 1, 1, 1, 0
3)1, 1, 0, 0, 1
4)1, 1, 0, 1, 0
Is there any way to calculate this without trying all the options?
I tried to use numpy, but I didn't find any function for counting with boolean variables.
you get all the solutions the same way you would for any system of linear equations:
0, 1, 1, 0, 1)you can then add any solution of the homogenous equation to the particular solution.
in your case: the system of equations (written as matrix) looks like:
[1 0 1 0 0]
[1 1 1 1 1]
[0 0 0 1 1]
[0 1 0 0 0]
if you apply gaussian elimination to that you get:
[1 0 1 0 0]
[0 1 0 0 0]
[0 0 0 1 1]
[0 0 0 0 0]
this is now meant to be multiplied with the vector of the variables. so the for the general solution to the homogenous equation can read off that the following must hold:
yh = 0 # from [0 1 0 0 0]
zh = xh # from [1 0 1 0 0]
wh = vh # from [0 0 0 1 1]
and you are free to choose xh and vh.
add any of those to the particular solution and you get all the solutions:
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)
to get:
0 1 1 0 1
0 1 1 1 0
1 1 0 0 1
1 1 0 1 0
there are no unnecessary loops. all settings of the variables are solutions to your equations.
Update:
(disclaimer: none of this is really tested...)
in order to get the echelon form of your equations, you could install galois and sympy and use them like this:
for this you need to:
pip install galois numpy sympy
then:
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)
gaussian elimination:
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)
i could not find a function in numpy that directly finds a particular solution. such a function might exist (?).
i counted the number of variables and the number of equations, set n_vars-n_eqs variables
to zero and hoped to find a solution for the remaining variables using 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)
then, for the general solution i used sympy (which is unaware of GF(2) and might not always work as expected?)
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}
the -z shows, that sympy does not know about GF(2). but in this case it works all the same.