MATLAB: Shuffle vector with constraints

constraintsshuffle

Hi,

I have an array of 50 1's, 50 2's, etc up to 50 8's. I would like to shuffle them with the constraint that two consecutive numbers cannot be the same. I tried several options but most are very cpu intensive or did not yield a good result. Are there computation efficient solutions to this problem?

Best Answer

A brute force method works fairly well in this scenario - 1) start with a shuffled version of the sequence, 2) find repeats, 3) swap any repeats to different locations... goto 2 (rinse and repeat). This sort of method would likely be terrible if you had fewer characters in your sequence, but for nine unique elements, it seems to halt very quickly.

Making your sequence:

seq = repmat([1:8],50,1); %make sequence

seq = [seq(:);repmat(9,30,1)]; %make sequence

Doing the reshuffling:

seq = seq(randperm(numel(seq))); %initial shuffle
old_idx= unique(find(diff(seq)==0));%find repeats

while ~isempty(old_idx), %continue until no repeats
    new_idx = unique(setdiff([1:length(seq)],old_idx)); %find new spots
    new_idx = new_idx((randi(length(new_idx),length(old_idx),1)))';
    seq([new_idx;old_idx],:) = seq([old_idx;new_idx],:); %swap
    old_idx= unique(find(diff(seq)==0));%find repeats
end

Related Solutions

MATLAB: Shuffle binary vector (n0 = n1) with constraints: number of consecutive repetitions

A brute force approach:

function V = ShuffledVector
x = 100;  % Number of elements, assumed to be even
Z = 5;
V = [true(1, x/2), false(1, x/2)];  % Half of elements is 1, rest is 0
found = false;
iter  = 0;
while ~found
    V      = V(randperm(x, x));
    [~, n] = RunLength(V);
    found  = all(n < Z);
    iter   = iter + 1;
end
end
function [b,n,idx] = RunLength(x)
% Or use the faster C-Mex function:
%   https://www.mathworks.com/matlabcentral/fileexchange/41813-runlength
x   = x(:);
d   = [true; diff(x) ~= 0];   % TRUE if values change
b   = x(d);                   % Elements without repetitions
k   = find([d', true]);       % Indices of changes
n   = diff(k);                % Number of repetitions
idx = k(1:length(k) - 1);     % Reply indices of changes
end

This permutes the complete vector if more than Z neighboring elements are equal. There larger Z is, the more efficient is this method. For x = 100 and Z = 10 one or two iterations are very likely, but for Z=3 you might wait for hours.

.An improvement is shuffle only elements from the blocks of equal values:

... % same as above
found = false;
iter  = 0;
V     = V(randperm(x, x));
while ~found
    % Find longest block of equal values:    

    [b, n, idx]    = RunLength(V);
    [maxN, maxInd] = max(n);
    if maxN > Z
       % One element of the largest block:        

       oldIdx    = idx(maxInd) + randi(maxN) - 1;
       % One element with a different value:

       other     = find(V ~= b(maxInd));  
       newIdx    = other(randi(numel(other)));
       % Swap values:

       swap      = V(oldIdx);
       V(oldIdx) = V(newIdx);
       V(newIdx) = swap;
    else
       found = true;
    end
    iter  = iter + 1;
end

This "bombing technique" chooses one element of the largest block of equal data and swaps its values randomly with other elements of V. Per iteration of the while loop, only one of these blocks is processed. It is very likely, that maxN occurs multiple times in n, so it might be better to include another loop:

... % same as above
found   = false;
maxIter = 1e9;
iter    = 0;
V       = V(randperm(x, x));
while ~found && iter < maxIter
    % Find longest block of equal values:    
    [b, n, idx] = RunLength(V);
    maxN        = max(n);
    if maxN > Z
       for maxInd = find(n == maxN)
         % One element of the largest block:        
         oldIdx    = idx(maxInd) + randi(maxN) - 1;
         % One element with a different value:
         other     = find(V ~= b(maxInd));  
         newIdx    = other(randi(numel(other)));
         % Swap values:
         swap      = V(oldIdx);
         V(oldIdx) = V(newIdx);
         V(newIdx) = swap;
       end
    else
       found = true;
    end
    iter  = iter + 1;
end
if ~found
    error('Cannot find solution in %d iterations!', iter)
end

Here I've added a security limit for the number of iterations.

For x = 100, Z = 5, this needs an average of 6 iterations.

MATLAB: Sorting and randomising a matrix according to a particular constraint.

Someone has kindly provided this very excellent solution that eradicates a lot of work and gives the perfect solution if anyone is interested:

   %# calculate index for the 1's and 2's
   r = rand(8,4);
   [~,idx12] = sort(r,2);
   %# calculate index for the 1's through 8's
   [~,idx8] = sort(r,1);
   %# use idx8 to shuffle idx12
   idx8into12 = bsxfun(@plus,idx8,[0 8 16 24]);
   %# now we can construct the output matrix
   B = [1 1;1 2;2 1;2 2];
   out = [B(idx12(idx8into12),:),idx8(:)];

Best Answer

Related Solutions

MATLAB: Shuffle binary vector (n0 = n1) with constraints: number of consecutive repetitions

MATLAB: Sorting and randomising a matrix according to a particular constraint.

Related Question