function [ x_num, x ] = i4mat_rref_solve_binary_nz ( m, n, nz, a, b )
%*****************************************************************************80
%
%% i4mat_rref_solve_binary_nz() seeks binary solutions of an IRREF system.
%
% Discussion:
%
% An MxN linear system A*x = b is considered.
%
% The matrix A and right hand side B are assumed to have been converted
% to integer row-reduced echelon form (IRREF).
%
% In order to solve a particular combinatorial problem, only binary
% solutions x are of interest; that is, each entry of x is either 0 or 1.
%
% Moreover, we know that exactly NZ of the variables are 1.
%
% The solution procedure involves two steps:
% * assign each free variable a value of 0 or 1, but never assign more
% that NZ nonzeroes;
% * solve for the dependent variables.
%
% We consider every possible assignment of free variables, and we save
% the solutions in which all the variables take on only 0 or 1 values.
%
% Licensing:
%
% This code is distributed under the GNU LGPL license.
%
% Modified:
%
% 08 September 2018
%
% Author:
%
% John Burkardt
%
% Input:
%
% integer M, N, the number of rows and columns.
%
% integer NZ, the number of nonzeros required in any binary
% solution.
%
% integer A(M,N), the IRREF matrix to be analyzed.
%
% integer B(M), the right hand side.
%
% Output:
%
% integer X_NUM, the number of binary solutions discovered.
% Note that there may be no binary solutions at all.
%
% integer X(N,X_NUM), the binary solutions, if any.
%
%
% Augment the original linear system to the NxN system A2 x = B2.
%
[ a2, b2, incon, freedom_num, freedom ] = i4mat_rref_system ( m, n, a, b );
%
% Initialize our list of solutions.
%
x_num = 0;
x = [];
%
% If FREEDOM_NUM < 0, then the system is overdetermined and cannot be solved.
%
if ( freedom_num < 0 )
return
end
%
% There are FREEDOM_NUM degrees of freedom, each of which could be set to 1.
% There must be NZ variables set to 1.
% Consider setting NZ2 degrees of freedom to 1, where NZ2 is between 0
% and the minimum of NZ and FREEDOM_NUM.
%
% Choose every possible selection of NZ2 degrees of freedom, and solve
% the system.
%
% If the resulting solution is binary, then add it to the list.
%
b_num = 0;
for nz2 = 0 : min ( nz, freedom_num )
done = true;
free_sub = [];
while ( true )
[ free_sub, done ] = ksub_next4 ( freedom_num, nz2, free_sub, done );
if ( done )
break;
end
b3 = b2;
b3(freedom(free_sub(1:nz2)),1) = 1;
b_num = b_num + 1;
y = i4mat_u_solve ( n, a2, b3 );
if ( i4vec_is_binary ( n, y ) )
x_num = x_num + 1;
x(1:n,x_num) = y(1:n,1);
end
end
end
return
end