Shuffle array while spacing repeating elements

user_5929023 0
Viewed 229

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.

shuffle matlab random arrays
2 Answers

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
user_65797440

If you just want to find one possible solution you could use something like that:

x = [1   1   1   2   2   2   3   3   3   3   3   4   5   5   6   7   8   9];
n = numel(x);
dist = 3;           %minimal distance
uni = unique(x);    %get the unique value
his = histc(x,uni); %count the occurence of each element
s = [sortrows([uni;his].',2,'descend'), zeros(length(uni),1)];

xr = [];            %the vector that will contains the solution

%the for loop that will maximize the distance of each element
for ii = 1:n
    s(s(:,3)<0,3) = s(s(:,3)<0,3)+1;
    s(1,3) = s(1,3)-dist;
    s(1,2) = s(1,2)-1; 
    xr = [xr s(1,1)];
    s = sortrows(s,[3,2],{'descend','descend'})
end

if any(s(:,2)~=0)
    fprintf('failed, dist is too big')
end

Result:

xr = [3   1   2   5   3   1   2   4   3   6   7   8   3   9   5   1   2   3]

Explaination:

I create a vector s and at the beggining s is equal to:

s =

   3   5   0
   1   3   0
   2   3   0
   5   2   0
   4   1   0
   6   1   0
   7   1   0
   8   1   0
   9   1   0

%col1 = unique element; col2 = occurence of each element, col3 = penalities

At each iteration of our for-loop we choose the element with the maximum occurence since this element will be harder to place in our array.

Then after the first iteration s is equal to:

s =

   1   3   0  %1 is the next element that will be placed in our array.
   2   3   0
   5   2   0
   4   1   0
   6   1   0
   7   1   0
   8   1   0
   9   1   0
   3   4  -3  %3 has now 5-1 = 4 occurence and a penalities of -3 so it won't show up the next 3 iterations.

at the end every number of the second column should be equal to 0, if it's not the minimal distance was too big.

user_43638640
Related