permutations of a matrix

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?

[David Hill]

% 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

[Stephen23]

@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:

Answer 1

[Stephen23]

Based on this efficient concept for generating a matrix of binary combinations:

https://www.mathworks.com/matlabcentral/fileexchange/55759-binary-string-generator

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.

[sam plant]

This is brilliant, thank you!

Answer 2

[Bruno Luong]

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(:)));

[Stephen23]

+1 very neat