MATLAB: Permutations of a matrix

binarycombinationsknapsackknapsack problemlinear algebralinear systemsmatricesmatrix algebrapermutationsstructural engineering

Hello,
for a linear system equation of Ax = B with A dimensions 5×5 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?

Best Answer

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.
Related Question