Rearrange elements in an array based on another array

6 views (last 30 days)
luca
luca on 25 Sep 2019
Edited: Jon on 26 Sep 2019
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?

Accepted Answer

Andrei Bobrov
Andrei Bobrov on 25 Sep 2019
Edited: Andrei Bobrov on 26 Sep 2019
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';
  3 Comments
Jon
Jon on 26 Sep 2019
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

Sign in to comment.

More Answers (1)

Jon
Jon on 25 Sep 2019
Edited: Jon on 25 Sep 2019
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

Products


Release

R2019b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by