Array Manipulation - randomly choosing elements

Question

Suppose I have an array of length N. I want to choose n positions randomly, make them zero and then add the existing elements to the next non-zero element.

For example, suppose r = (r1,r2,r3,r4,r5), N = 5. Let n = 2. And the randomly picked positions are 3rd and 4th. Then I want to transform r to r_new = (r1, r2, 0, 0, r3+r4+r5).

Instead if the randomly selected positions were 1 and 3, then I want to have r_new = (0, r1 + r2, 0, r3+r4, r5).

I am coding in MATLAB. Here is my current code.

u   = randperm(T);
ind = sort(u(1:n(i)));
tmp = r(ind);
r(ind) = 0;

x = find( r );

I am not necessarily looking for MATLAB code. Pseudocode would be helpful enough.

Answer 1

I'm assuming the last position can never be selected, otherwise the intended behaviour is undefined. So you randomly select n positions uniformly distributed from 1 up to N-1 (not up to N).

Here's one approach:

1. Select n distinct random positions from 1 to N-1, and sort them. Call the resulting vector of positions pos. This can be easily done with randperm and sort.
2. For each value in pos, say p, accumulate r(p) into r(p+1), and set r(p) to zero. This is done with a for loop.

In step 2, if position p+1 happens to belong to pos too, the accumulated value will be moved further to the right in a subsequent iteration. This works because pos has been sorted, so the randomly selected positions are processed from left to right.

r = [3 5 4 3 7 2 8]; %// data
n = 2; %// number of positions
pos = sort(randperm(numel(r)-1,n)); %// randomly select positions, and sort them
for p = pos
    r([p p+1]) = [0 r(p)+r(p+1)]; %// process position p
end