How to keep a specific value in binary matrix with column constraint?
Show older comments
Hello!
i have a binary matrix A(10*10) , i want to return '1' to '0' to get a single one in each row. I'm wondering how I can do this, knowing that I can keep a '1' in different columns except the last column, i.e. the last column cannot contain a '1'.
A [1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1]
Accepted Answer
Fangjun Jiang
on 9 Sep 2022
Edited: Fangjun Jiang
on 9 Sep 2022
N=10;
A=eye(N);
B=A(:,randperm(N));% shuffle the Identity matrix randomly
RandCol=randi(N-1);
B(:,RandCol)=B(:,RandCol)+B(:,end);% move the 1 in last column randomly to the left
B(:,end)=0
% To verify
sum(B)
sum(B,2)
27 Comments
Maria
on 9 Sep 2022
Fangjun Jiang
on 9 Sep 2022
There are many "1"s in each row in your A matrix. How do you "keep just a single 1 in each row"? If the final matrix has just a single 1 in each row, would that effectively be the eye() matrix being shuffled? Of course, the last column is all zeros.
Fangjun Jiang
on 9 Sep 2022
That is true. I thought it was not critical.
Okay then, any logic how to change "1" to "0" in each row?
It will be very easy to set the last column to be all zero first. Then, just randomly pick only one 1 in each row and set all others to be zero?
Maria
on 9 Sep 2022
This code should work. I changed A for the purpose of setting special cases, assume there must have at lease one 1 in the first 9 columns in each row.
%%
A =[1 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 1
1 1 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1];
B=zeros(size(A));
for k=1:size(A,1)
index=find(A(k,1:end-1));
select=randperm(length(index),1);
B(k,index(select))=1;
end
sum(B)
sum(B,2)
Maria
on 9 Sep 2022
Fangjun Jiang
on 9 Sep 2022
Edited: Fangjun Jiang
on 9 Sep 2022
That is when you have a row where column 1 to 9 are all zeros.
I guess that is still valid. You need to change 1 to 0. If all zero, then do nothing. update below
B=zeros(size(A));
for k=1:size(A,1)
index=find(A(k,1:end-1));
if isempty(index),continue;end
select=randperm(length(index),1);
B(k,index(select))=1;
end
Maria
on 9 Sep 2022
So the number of 1's in each column can be arbitrary ?
A =[1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1];
B=zeros(size(A));
for k=1:size(A,1)
index=find(A(k,1:end-1));
select=randperm(length(index),1);
B(k,index(select))=1;
end
B
Maria
on 10 Sep 2022
Fangjun Jiang
on 12 Sep 2022
B=zeros(size(A));
for k=1:size(A,1)
index=find(A(k,:));
if isempty(index),continue;end
select=randperm(length(index),1);
B(k,index(select))=1;
end
Fangjun Jiang
on 16 Sep 2022
Edited: Fangjun Jiang
on 16 Sep 2022
It follows a similar technique as above. Here you go:
%%
A=ones(50,10); % just an example data
%%
B=zeros(size(A));
% First phase, loop through each row, find all existing 1s, randomly pick
% one, set all others to zero
for k=1:size(A,1)
index=find(A(k,:));
if isempty(index),continue;end
select=randperm(length(index),1);
B(k,index(select))=1;
end
sum(B)
%sum(B,2)
%%
C=zeros(size(B));
% Second phase, loop through each column, find all existing 1s,
% If less than or equal to 5, do nothing
% If more than 5, randomly pick five, set all others to zero
for k=1:size(B,2)
index=find(B(:,k));
if length(index)<=5
C(:,k)=B(:,k);
continue;
end
select=randperm(length(index),5);
C(index(select),k)=1;
end
sum(C)
%sum(C,2)
%sum(C,2)
Torsten
on 16 Sep 2022
You might delete '1's in the second phase such that some rows become zero rows, don't you ?
Maria
on 16 Sep 2022
Fangjun Jiang
on 16 Sep 2022
Yes. Thinking of this ...
- Make sure each row is all zeros, or has at most one 1 in the entire row. That is easy to do.
- Based on the result above, apparently, some columns have more then five ones, so you want to change some of them into 0.
- Then some rows will become all-zero, even if previously there was no all-zero rows.
- It is possible that in above step 1, instead of randomly pick one 1, there is an algorithm to pick them so the distribution of 1s is evenly distributed between columns.
- That algorithm is not provided.
- For a matrix that has more rows than columns, the all-zero rows have to happen, depending on the number of rows and the threshold value (5 in the example above).
- For a square matrix, this is very unlikely to happen if the threshold value is 5.
- For a square matrix, it is possible during the phase one (loop through rows), that all the previously used index numbers are removed. In that case, if A starts to be ones(10), then the end result C would be a shuffled eye(10).
Torsten
on 16 Sep 2022
And the procedure should be the same as before:
You have a binary matrix. For each row, you determine the last column with '1' as entry.
Then for each row, you find the columns < the last column with '1' as entry, choose arbitrarily one such column and write a '1' at this position of a matrix N which was initialized as 0-matrix.
Finally, the matrix N should not contain more than a predefined number of '1''s in each column.
?
Fangjun Jiang
on 16 Sep 2022
Please don't delete your comments. Otherwise, the thread doesn't make sense.
What is the size of your matrix A? Is it always square?
Maria
on 16 Sep 2022
Say A is an (mxn) binary matrix.
First remove the rows of A that contain only one '1' (they will become zero rows in B).
For the resulting matrix A, switch the last '1' in each row to a '0'.
Then solve the following optimization problem using "intlinprog" with the elements of B being the unknowns:
max: sum(sum((A-B))
s.c.
sum_{j=1}^{j=n} b_ij = 1 for 1 <= i <= m
sum_{i=1}^{i=m} b_ij <= 5 (or whatever you chose as maximum number of 1's per column) for 1 <= j <= n
0 <= b_ij <= 1
b_ij integer
If the value of the objective function after optimization is nnz(A)-m, you succeeded and the problem was feasible. Else, no solution exists.
Maria
on 16 Sep 2022
Torsten
on 16 Sep 2022
You didn't write this anywhere - so I treated the case that there can be rows with only one '1'.
If this is not the case, skip the line
First remove the rows of A that contain only one '1' (they will become zero rows in B).
in my comment.
Fangjun Jiang
on 16 Sep 2022
Edited: Torsten
on 16 Sep 2022
Okay, this is getting more and more into your actual work. I will provide this as the last answer.
%%
N_row=100;
N_col=60;
A=ones(N_row,N_col); % just an example data
%%
B=zeros(N_row,N_col);
ColSumMax=5;
% First phase, loop through each row, find all existing 1s, randomly pick
% one, set all others to zero
for k=1:size(A,1)
index=find(A(k,:));
if isempty(index),continue;end
% comment out this part of the code to see the difference
% check if the sum of any column already exceeds 5, if Yes, remove the
% column number from the index so 1 won't be allocated to this column
ColumnsMaxedOut=find(sum(B(1:k,:),1)>ColSumMax);
if ~isempty(ColumnsMaxedOut)
index=setdiff(index,ColumnsMaxedOut);
end
% need to do this check again
if isempty(index),continue;end
select=randperm(length(index),1);
B(k,index(select))=1;
end
check=sum(B)
any(check>5)
Maria
on 16 Sep 2022
Maria
on 16 Sep 2022
More Answers (1)
Your last question was quite interesting - so I invested some time ...
If A becomes larger, you will have to work with sparse inputs to intlinprog.
%rng('default')
% n = 100; % number of rows of A
% m = 60; % number of columns of A
n = 200; % number of rows of A
m = 120; % number of columns of A
bound_ones = 5; % bound for column sums of B
A = randi([0 1],n,m); % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
display('Matrix A inappropriate.');
return
end
s = nnz(A);
%
% Objective function
% max: sum_ij cij = sum_ij (aij - bij)
% is equivalent to
% min: -sum_ij cij = -sum_ij (aij - bij)
f = [zeros(n*m,1);-ones(n*m,1)];
%f = zeros(2*n*m,1);
%
% Equality constraints
% cij = aij - bij
Aeq1 = zeros(n*m,2*n*m);
beq1 = zeros(n*m,1);
counter = 0;
for i = 1:n
for j = 1:m
counter = counter + 1;
Aeq1(counter,counter) = 1.0;
Aeq1(counter,counter+n*m) = 1.0;
beq1(counter) = A(i,j);
end
end
%sum_j bij = 1 (1 <= i <= n)
Aeq2 = zeros(n,2*n*m);
beq2 = zeros(n,1);
for i = 1:n
Aeq2(i,(i-1)*m+1:i*m) = 1.0;
beq2(i) = 1.0;
end
%Concatenate equality constraints
Aeq = [Aeq1;Aeq2];
beq = [beq1;beq2];
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
Aineq = zeros(m,2*n*m);
bineq = zeros(m,1);
for j = 1:m
Aineq(j,j:m:(n-1)*m+j) = 1.0;
bineq(j) = bound_ones;
end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= bij <= 1 and cij = aij - bij >= 0
lb = zeros(2*n*m,1);
ub = [ones(n*m,1);Inf*ones(n*m,1)];
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
%
% s + fval should equal n if x is a solution
n
s + fval
if exitflag == 1
B = x(1:n*m);
B = reshape(B,m,n).';
C = x(n*m+1:2*n*m);
C = reshape(C,m,n).';
% Check constraints
any(C~=A-B,'All')
any(C<0,'All')
any((0>B)|(B>1),'All')
any(sum(B,2)~=1)
any(sum(B,1)>bound_ones)
else
display('Matrix B does not exist')
end
B
4 Comments
Maria
on 18 Sep 2022
Here is an easier version with less optimization variables:
%rng('default')
% n = 100; % number of rows of A
% m = 60; % number of columns of A
n = 1000; % number of rows of A
m = 1000; % number of columns of A
bound_ones = 5; % bound for column sums of B
A = randi([0 1],n,m); % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
display('Matrix A inappropriate.');
return
end
%
% Objective function
% min: sum_ij bij
f = ones(n*m,1);
% Alternatively:
% Only search for feasible point where objective doesn't matter
%f = zeros(n*m,1);
%
% Equality constraints
%sum_j bij = 1 (1 <= i <= n)
Aeq = zeros(n,n*m);
beq = zeros(n,1);
for i = 1:n
Aeq(i,(i-1)*m+1:i*m) = 1.0;
beq(i) = 1.0;
end
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
Aineq = zeros(m,n*m);
bineq = zeros(m,1);
for j = 1:m
Aineq(j,j:m:(n-1)*m+j) = 1.0;
bineq(j) = bound_ones;
end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= b_ij <= a_ij
lb = zeros(n*m,1);
ub = reshape(A.',[],1);
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
%
% fval should equal n if x is a solution
n
fval
if exitflag == 1
B = reshape(x,m,n).';
% Check constraints
any(B>A,'All')
any((B<0)|(B>1),'All')
any(sum(B,2)~=1)
any(sum(B,1)>bound_ones)
else
display('Matrix B does not exist')
end
B
%rng('default')
% n = 100; % number of rows of A
% m = 60; % number of columns of A
n = 1500; % number of rows of A
m = 1000; % number of columns of A
bound_ones = 5; % bound for column sums of B
A = randi([0 1],n,m); % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
display('Matrix A inappropriate.');
return
end
%
% Objective function
% min: sum_ij bij
f = ones(n*m,1);
% Alternatively:
% Only search for feasible point (objective doesn't matter)
%f = zeros(n*m,1);
%
% Equality constraints
%sum_j bij = 1 (1 <= i <= n)
ir = zeros(n*m,1);
ic = zeros(n*m,1);
v = zeros(n*m,1);
for i = 1:n
ir((i-1)*m+1:i*m) = i;
ic((i-1)*m+1:i*m) = (i-1)*m+1:i*m;
v((i-1)*m+1:i*m) = 1.0;
end
Aeq = sparse(ir,ic,v,n,n*m);
beq = ones(n,1);
%Aeq = zeros(n,n*m);
%beq = zeros(n,1);
%for i = 1:n
% Aeq(i,(i-1)*m+1:i*m) = 1.0;
% beq(i) = 1.0;
%end
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
ir = zeros(n*m,1);
ic = zeros(n*m,1);
v = zeros(n*m,1);
for j = 1:m
ir(j:m:(n-1)*m+j) = j;
ic(j:m:(n-1)*m+j) = j:m:(n-1)*m+j;
v(j:m:(n-1)*m+j) = 1.0;
end
Aineq = sparse(ir,ic,v,m,n*m);
bineq = bound_ones*ones(m,1);
%Aineq = zeros(m,n*m);
%bineq = zeros(m,1);
%for j = 1:m
% Aineq(j,j:m:(n-1)*m+j) = 1.0;
% bineq(j) = bound_ones;
%end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= b_ij <= a_ij
lb = zeros(n*m,1);
ub = reshape(A.',[],1);
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
%
% fval should equal n if x is a solution
n
fval
if exitflag == 1
B = reshape(x,m,n).';
% Check constraints
any(B>A,'All')
any((B<0)|(B>1),'All')
any(sum(B,2)~=1)
any(sum(B,1)>bound_ones)
else
display('Matrix B does not exist')
end
B
Categories
Find more on Solver Outputs and Iterative Display in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
