MATLAB Answers

0

permutations of a matrix

Asked by sam plant on 23 Aug 2019 at 11:56
Latest activity Edited by Bruno Luong
on 23 Aug 2019 at 14:26
Hello,
for a linear system equation of Ax = B with A dimensions 5x5 and x, a column vector. Let's say A is a binary matrix of 1's and 0's and i had the cases of having 3 1's and the rest 0's in A, or 5 1's and the rest 0's. How would I calculate the values of B for all combinations of A consisting of 3 or 5 1's?

  2 Comments

David Hill on 23 Aug 2019 at 13:43
% broot-force for 3 1's if I understood you correctly.
x=[1 0 1 0 1]';% any column vector
y=nan(5,1,2300);
z=zeros(5);
count=0;
for i=1:25
z(i)=1;
for j=i+1:25
z(j)=1;
for k=j+1:25
z(k)=1;
count=count+1;
y(:,1,count)=z*x;
z(k)=0;
end
z(j)=0;
end
z(i)=0;
end
Stephen Cobeldick on 23 Aug 2019 at 14:14
@David Hill: you should put that as an answer.
There are also answers on this forum that discuss how you could generalize that concept, so that it does not use a fixed number of nested for loops:

Sign in to comment.

2 Answers

Answer by Stephen Cobeldick on 23 Aug 2019 at 12:54
Edited by Stephen Cobeldick on 23 Aug 2019 at 13:07
 Accepted Answer

Based on this efficient concept for generating a matrix of binary combinations:
you can efficiently create a matrix of the required combinations, by incrementally adding to a matrix and removing the superfluous rows at each loop iteration, thus avoiding any out-of-memory issues (as would happen if you tried to generate all combinations at once).
s = 3; % how many 1's in matrix.
x = [1;2;3;4;5]; % your column vector.
Generate matrix of all combinations:
n = numel(x); % matrix has size n*n
m = [0;1]; % seed matrix.
for k = 2:n*n
r = size(m,1);
m = [zeros(r,1),m;ones(r,1),m];
m(sum(m,2)>s,:) = []; % remove rows where sum > s
end
m(sum(m,2)~=s,:) = []; % remove rows where sum ~= s
For s=3 I get 2300 rows (i.e. each row is a unique combination), and for s=5 I get 53130 rows. You can easily check that each row sums to s (i.e. 3 or 5):
>> all(sum(m,2)==3)
ans = 1
and that the rows are unique:
>> size(unique(m,'rows'),1)==size(m,1)
ans = 1
Then you can simply loop over those rows, reshape each row into a matrix, and do whatever operations you want:
r = size(m,1);
B = cell(r,1); % preallocate!
for k = 1:r
A = reshape(m(k,:),n,n);
B{k} = A*x; % whatever operations you want...
end
The first few outputs are:
>> B{1:3}
ans =
0
0
5
5
5
ans =
0
5
0
5
5
ans =
0
5
5
0
5
Do this once for s=3, and once for s=5.

  1 Comment

sam plant on 23 Aug 2019 at 13:07
This is brilliant, thank you!

Sign in to comment.


Bruno Luong
Answer by Bruno Luong
on 23 Aug 2019 at 14:06
Edited by Bruno Luong
on 23 Aug 2019 at 14:26

x = (1:5)';
n = size(x,1);
m = 5; % size of b
s = 3; % target sum(A(:))
[i,k] = ind2sub([m,n],nchoosek(1:m*n,s));
j = repmat((1:size(i,1))',s,1);
% each column of B is a possible vector of the set
% { b=A*x: A (m x n) binary matrix such that sum(A(:))=s }
B = accumarray([i(:) j], x(k(:)));

  1 Comment

Stephen Cobeldick on 23 Aug 2019 at 14:22
+1 very neat

Sign in to comment.