Rearrange elements in an array based on another array

Hi,

given the following matrix

V=
[12   11    9     8     10    6     8     7     9     5     4     6      9;
8     10    7     8     9     8     4     4     12    12    6     6      10]

and

M=
[0    23    10    1     0     0     12    0     23    0     0     0      0;
0     23    11    0     0     0     15    0     20    0     0     0      0]

I want to rearrange the ROWS of M matrix on the basis of V.

Considering just the first rows of V and M

12   11    9     8     10    6     8     7     9     5     4     6      9

0    23    10    1     0     0     12    0     23    0     0     0      0

the cumulative sum of the M row is (23+11+1+12+23)=70

Now in the zero places of M row just put the value in the same column of row V, and put 0 in the non zero values, obtaining

12   0    0     0     10    6     0     7     0     5     4     6      9      %SUM 59

the cumulative sum of this new vector is 59. So from now on we want to put 1 in the zeros places till we reach 70. So

12   1    1     1     10    6     1     7     1     5     4     6      9        %SUM 64

Then again

12   2    2     2     10    6     2    7     2     5     4     6      9        %SUM 69

And finally

12   3    2     2     10    6     2    7     2     5     4     6      9        %SUM 70

Now the cumulative sum is the same as the beginning (70)

So the basic idea is to put in the zeros places of M the value of the corresponding places in V, and then, try to reduce as much as possible the other places (that were the no zero places in M)

May someone help me with this task?

Answer 1

[Andrei Bobrov]

s = sum(M,2);
v = V.*(M == 0);
ss = s - sum(v,2);
lo = ss > 0;
n = sum(v == 0,2);
a = fix(ss./n);
b = mod(ss,n);
add = arrayfun(@(n,a,b)ones(n,1)*a + [ones(b,1);zeros(n-b,1)],n,a,b,'un',0);
vv = v(ss > 0,:)';
vv(vv == 0) = cat(1,add{lo});
v(lo,:) = vv';

[Jon]

Actually this produces an error for some cases. For example using

V =...
    [24    14    14    13    19     4
     5     4     9    15    12     7
    26    25    21    21    25    10]


M = ...
[
     0     0    23     0     0    30
    14    22     0     0     0    26
    29     0    28    22     0    24]

Produces the error:

Error using horzcat

Dimensions of arrays being concatenated are not consistent.

Error in mbv2 (line 80)

vv(vv == 0) = [add{lo}];

[Andrei Bobrov]

Hi Jon! Thanks for reply. I am fix.

[Jon]

This seems to work for most cases now. One other edge case that would cause a problem is if M has a row of all zeros. @Luca will you ever get an M with a row of all zeros?

The reason I came across this was I was curious to see how much the performance improves with Andrei's nice vectorization and use of arrayfun, compared with my loop approach. Timing it with large number of randomly assigned matrices on average it seems that Andrei's vectorized approach runs about 25% faster. That is, if the execution time of Andrei's is Tvector and the execution time of the explicit loop approach is Tloop I find that typicallly (1/Tvector)/(1/Tloop) = 1.25

Answer 2

[Jon]

While I was working on this I see that @Andrei has already posted a very nice vectorized solution. In case it is helpful, here is another approach, which uses a loop, but perhaps the logic is more obvious.

By the way, I think you have a small mistake in your example, where you say "the cumulative sum of the M row is (23+11+1+12+23)=70" In fact I think that should be (23+10+1+12+23)=69, and so the new row should be

12 2 2 2 10 6 2 7 2 5 4 6 9

not

12 3 2 2 10 6 2 7 2 5 4 6 9 %SUM 70

I'm curious what the motivation for this problem is, what is this type of manipulation used for?

% 
V = ...
[12   11    9     8     10    6     8     7     9     5     4     6      9;
8     10    7     8     9     8     4     4     12    12    6     6      10];

M = ...
[0    23    10    1     0     0     12    0     23    0     0     0      0;
0     23    11    0     0     0     15    0     20    0     0     0      0];

% get some dimensions
[numRows,numCols] = size(V); % assume M is same size

% preallocate array to hold result
R = zeros(numRows,numCols);
% loop through rows of input matrices
numRows = size(V,1);
for k = 1:numRows
    
    
    % find locations  of zeros in current row of M
    idz = find(M(k,:)==0); 
    
    % find indices where ones are to be added in new vector
    iPlaces = find(~M(k,:)==0);
    
    % find number of locations where ones are to be added
    numPlaces = length(iPlaces);
    
    % initialize new row
    R(k,idz) = V(k,idz);
    
    % find column sum of current row of M
    mSum = sum(M(k,:));
    
    % find total number of ones that need to be added to match original
    % column sum
    numNeeded = max(0,mSum - sum(R(k,:))); % number needed must be non-negative
    
   % determine how many ones to put into each place
   q = floor(numNeeded/numPlaces); % quotient
   r = rem(numNeeded,numPlaces); % remainder
   R(k,iPlaces(1:r)) = q + 1; %one more need for the first r elements
   R(k,iPlaces(r+1:end)) = q;
   

end

   
   
    
    

[luca]

thanks a lot Jon