Shuffle array while spacing repeating elements

Question

I'm trying to write a function that shuffles an array, which contains repeating elements, but ensures that repeating elements are not too close to one another.

This code works but seems inefficient to me:

function shuffledArr = distShuffle(myArr, myDist)
% this function takes an array myArr and shuffles it, while ensuring that repeating 
% elements are at least myDist elements away from on another    

% flag to indicate whether there are repetitions within myDist
reps = 1;
while reps 

    % set to 0 to break while-loop, will be set to 1 if it doesn't meet condition
    reps = 0;  

    % randomly shuffle array
    shuffledArr = Shuffle(myArr);

    % loop through each unique value, find its position, and calculate the distance to the next occurence
    for x = 1:length(unique(myArr))
        % check if there are any repetitions that are separated by myDist or less
       if any(diff(find(shuffledArr == x)) <= myDist)
           reps = 1;
       break;
   end
end
end

This seems suboptimal to me for three reasons:

1) It may not be necessary to repeatedly shuffle until a solution has been found.

2) This while loop will go on forever if there is no possible solution (i.e. setting myDist to be too high to find a configuration that fits). Any ideas on how to catch this in advance?

3) There must be an easier way to determine the distance between repeating elements in an array than what I did by looping through each unique value.

I would be grateful for answers to points 2 and 3, even if point 1 is correct and it is possible to do this in a single shuffle.

Answer 1

I think it is sufficient to check the following condition to prevent infinite loops:

[~,num, C] = mode(myArr);
N = numel(C);
assert( (myDist<=N)  || (myDist-N+1) * (num-1) +N*num <= numel(myArr),...
'Shuffling impossible!');

Assume that myDist is 2 and we have the following data:

[4 6 5 1 6 7 4 6]

We can find the the mode , 6, with its occurence, 3. We arrange 6s separating them by 2 = myDist blanks:

6 _ _ 6 _ _6

There must be (3-1) * myDist = 4 numbers to fill the blanks. Now we have five more numbers so the array can be shuffled.

The problem becomes more complicated if we have multiple modes. For example for this array [4 6 5 1 6 7 4 6 4] we have N=2 modes: 6 and 4. They can be arranged as:

6 4 _ 6 4 _ 6 4 

We have 2 blanks and three more numbers [ 5 1 7] that can be used to fill the blanks. If for example we had only one number [ 5] it was impossible to fill the blanks and we couldn't shuffle the array.

For the third point you can use sparse matrix to accelerate the computation (My initial testing in Octave shows that it is more efficient):

function shuffledArr = distShuffleSparse(myArr, myDist)
    [U,~,idx] = unique(myArr);
    reps = true;
    while reps 
        S = Shuffle(idx);
        shuffledBin = sparse ( 1:numel(idx), S, true, numel(idx) + myDist, numel(U) );
        reps = any (diff(find(shuffledBin)) <= myDist);
    end
    shuffledArr = U(S);
end

Alternatively you can use sub2ind and sort instead of sparse matrix:

function shuffledArr = distShuffleSparse(myArr, myDist)
    [U,~,idx] = unique(myArr);
    reps = true;
    while reps 
        S = Shuffle(idx);
        f = sub2ind ( [numel(idx) + myDist, numel(U)] , 1:numel(idx), S );
        reps = any (diff(sort(f)) <= myDist);
    end
    shuffledArr = U(S);
end