Generating all solutions to an under-determined system of equations with a restriction-CodePudding

I have an under-determined system of equations in which the solutions are either 0 or 1 for each variable and each variable coefficient is 1. Is there a way to generate all possible solutions? For example, if the system only has the equation a1 a2=1, then the solutions are [1,0] or [0,1] (where each index in the list corresponds to a variable). Another thing to consider is that I do not have the number of variables before the code is executed, so I do not know how I would declare the variable names, which are in a list that gets updated while the code is running, with a function like symbol() from SymPy, which is the library I commonly see being used to solve linear systems, but which I also don't know how could be used in this case.

A brute force way would be to generate all possible combinations of 0s and 1s, and then filter only those that work, but it could get slow really quickly.

CodePudding user response：

SymPy's linsolve can give a parametric representation of the solution of an underdetermined system of linear equations:

In [128]: a1, a2, a3, a4 = symbols('a1, a2, a3, a4')

In [129]: eqs = [Eq(a1   a2, 1), Eq(a3   a4   a1, 1)]

In [130]: linsolve(eqs, [a1, a2, a3, a4])
Out[130]: {(-a₃ - a₄   1, a₃   a₄, a₃, a₄)}

The task then it just to assign possible values to the remaining parameters. In this case you have 4 choices given a1 and a4 could each be 0 or 1. Substituting those values will show if a1 and a2 are within the expected range which rules out the case a3 = a4 = 1 leaving the three remaining cases. I won't give code showing how to go on from here because you haven't given any code or spelled out any example of what the equations might look like.

Ultimately I don't think there's any way to avoid the combinatoric explosion of possibilities but you can at least reduce the brute force approach to the dimension of the nullspace of the matrix by getting a parametric solution. The example above demonstrates reducing the number of cases from 16 to 4 but the reduction could be more dramatic for a larger system. That may or may not apply to your case depending on many things that you haven't specified in your question.

CodePudding user response：

If the lhs is n and you have M variables a1 ... am, then this is the same problem as finding all the combinations of n choices from among the M variables.

There is a function to do this in itertools.

For the case a1 a2 a3 = 2, that is, when you have 3 variables and rhs is 2 (Code shamelessly stolen from GeeksforGeeks, with slight modifications):

from itertools import combinations
  
# Get all combinations of a1, a2, a3 and length 2
comb = combinations(['a1', 'a2', 'a3'], 2)
  
# Print the obtained combinations
for i in comb:
    print('   '.join(i))

Result:

a1   a2
a1   a3
a2   a3

If you want to get the result in the form of arrays:

from itertools import combinations
import numpy as np

n = 2  # RHS
m = 3  # number of variables on LHS

c = combinations(np.arange(m), n)
for cc in c:
    tmp = np.zeros(m)
    tmp[list(cc)] = 1
    print(tmp)

Result:

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