Geek Answers Handbook

Extract matrix elements

If I have a matrix:

0 0 3 4 4 3 2 0 2 0 2 0

I want to extract non-zero elements in some batches in relation to the rule: if an element is already taken, another element in the same row / column is not allowed. Thus, the extracted matrix will be:
1st party:

 0 0 3 0 4 0 0 0 0 0 0 0

Second batch:

 0 0 0 4 0 3 0 0 0 0 2 0

Third party:

 0 0 0 0 0 0 2 0 2 0 0 0

Any other combination of batches is also accepted if all nonzero elements are covered and the rule is true. How do you do this in MATLAB / Octave?

+4
source share
3 answers

Gunther was already on the right track. Do you want to select an item if

  • string cumsum non-zeros 1 AND
  • column cumsum non-zeros 1 AND
  • the element itself is not equal to zero.

The following code solves the problem:

 A = [0, 0, 3, 4; 4, 3, 2, 0; 2, 0, 2, 0]; batches = cell(0); while any(A(:)~=0) selector = cumsum(A~=0, 1) .* cumsum(A~=0, 2) .* (A~=0) == 1; batches{end+1} = A .* selector; A(selector) = 0; end

Please note that the returned solution is not optimal, as its second batch

 0 0 0 4 0 3 0 0 2 0 0 0

which means that the remaining elements of the matrix belong to one column:

 0 0 0 0 0 0 2 0 0 0 2 0

Unfortunately, you cannot draw them in one batch. Thus, you get four batches instead of three.

Edit: Perhaps it is a good idea to first select those items that appear in rows / columns with lots of non-zero items. For example, you can use these weights.

 weight = repmat(sum(A~=0, 1), size(A, 1), 1) ... .* repmat(sum(A~=0, 2), 1, size(A, 2)) .* (A~=0) weight = 0 0 6 2 6 3 9 0 4 0 6 0

Next algorithm

 batches = cell(0); while any(A(:)~=0) batch = zeros(size(A)); weight = repmat(sum(A~=0, 1), size(A, 1), 1) ... .* repmat(sum(A~=0, 2), 1, size(A, 2)) .* (A~=0); while any(weight(:)~=0) [r,c] = find(weight == max(weight(:)), 1); batch(r,c) = A(r,c); A(r,c) = 0; weight(r,:) = 0; weight(:,c) = 0; end batches{end+1} = batch; end

returns these parties.

 batches{:} ans = 0 0 0 4 0 0 2 0 2 0 0 0 ans = 0 0 3 0 4 0 0 0 0 0 0 0 ans = 0 0 0 0 0 3 0 0 0 0 2 0

So he worked, at least for this little test case.

+2
source

For strings only, I would do it like this:

 A = [ 0 0 3 4 ; 4 3 2 0 ; 2 0 2 0 ];

  • Checking that the numbers are nonzero:

     Anonzero=A~=0; >> Anonzero 0 0 1 1 1 1 1 0 1 0 1 0

  • Take cumsum along the lines of Anonzero :

     Aidx=cumsum(A,[],2); >> Aidx 0 0 1 2 1 2 3 3 1 1 2 2 numbatches=max(Aidx(:,end));

  • Set indexes of zero values ​​back to zero, so they will not be selected

     A(~Anonzero)=0;

  • Extract batches:

     batch=cell(numbatches,1); for ii=1:numbatches batch{ii}=A.*(Aidx==ii); end

as a result of:

 >>batch{1} 0 0 3 0 4 0 0 0 2 0 0 0 >>batch{2} 0 0 0 4 0 3 0 0 0 0 2 0 >>batch{3} 0 0 0 0 0 0 2 0 0 0 0 0

I suppose something similar could be done for the row and column rule, but I do not see it right away. I will think about it;)

+3
source

An interesting problem, no doubt ... I assume that the @GuntherStruyf method will eventually become the one you should choose. However, here's a simplified solution using loops:

 A = [ 0 0 3 4 4 3 2 0 2 0 2 0 ]; C = {}; nz = A ~= 0; while any(nz(:)) tmpNz = nz; tmpA = A; newNz = false(size(nz)); while true [i,j] = find(tmpNz, 1); if isempty(i) || isempty(j), break; end tmpNz(i,:) = false; tmpNz(:,j) = false; newNz(i,j) = true; end tmpA(~newNz) = false; C{end+1} = tmpA; nz(newNz) = false; end

This should be pretty fast as soon as you get rid of the growing array of cells, for example by first distributing it with a large number of source elements and then deleting unused elements.

However, I will wait until @GuntherStruyf selects it!

+2
source

More articles:


All Articles