Randomize vector avoiding consecutive values

I have this vector "leftSideProbes_random" and I would like to shuffle the values so that in the final vector the values do not appear consecutively (e.g., two same values do not appear in succession).

leftSides = [1,3,5];
leftPos_trials = repmat(leftSides,1,14);
leftSideProbes_random = randsample(leftPos_trials,42);
leftSideProbes=leftSideProbes_random(randperm(42));

I've tried randperm and other different alternatives, but none of them seem to work.

Any help would be very much appreciated.

Thanks,

Mikel

[Torsten]

I have this vector "leftSideProbes_random" and I would like to shuffle the values so that in the final vector the value does not appear consecutively.

Depending on what "randsample" returns, this will not be possible in all cases.

Further, if you want that in the final vector two same values do not appear consecutively, it's no longer random.

Answer 1

[Voss]

Here's a method that picks values randomly, one at a time, from a set that excludes the most recently picked value

leftSides = [1,3,5];
n_reps = 14;

n = numel(leftSides);
all_idx = 1:n;
result = zeros(1,n*n_reps);
result(1) = randi(n);
available = true(1,n);
for ii = 2:n*n_reps
    available(result(ii-1)) = false;
    temp_idx = all_idx(available);
    result(ii) = temp_idx(randi(n-1));
    available(result(ii-1)) = true;
end
leftPos_trials = leftSides(result)

leftPos_trials = 1×42

5 3 5 1 5 1 3 5 3 1 3 1 5 3 1 5 3 5 3 1 3 1 5 1 3 1 3 1 3 1

find(diff(leftPos_trials) == 0) % check for consecutive repeats

ans =

  1×0 empty double row vector

[Mikel Jimenez]

This seems to be working fine, thanks! I was hoping to accomplish this on a simpler code, but apparently it is not possible...Thanks for your help.

[Mikel Jimenez]

Hi Voss, I have one related question. In this code you kindly provided I get a 96 integer vector, but now, I need the size of the vector to be 103. I've been trying it in different ways but it seems I can't get it right yet.

Do you think it is possible to create this odd-sized vector array from an even-sized vector, similar to the original code?

[Voss]

leftSides = [1,3,5];
n_total = 103;

n = numel(leftSides);
all_idx = 1:n;
result = zeros(1,n_total);
result(1) = randi(n);
available = true(1,n);
for ii = 2:n_total
    available(result(ii-1)) = false;
    temp_idx = all_idx(available);
    result(ii) = temp_idx(randi(n-1));
    available(result(ii-1)) = true;
end
leftPos_trials = leftSides(result)

leftPos_trials = 1×103

3 5 1 3 1 3 5 1 3 1 5 3 5 3 5 3 5 1 3 5 1 5 3 5 3 5 1 5 3 5

find(diff(leftPos_trials) == 0) % check for consecutive repeats

ans =

  1×0 empty double row vector

[Mikel Jimenez]

Thanks a lot! One further question, I'd need the different numbers to appear equally in the vector, the output here produces some variance for each value...

The initial vector I have is: allPos = [1,2,3,4,5,6], the rest of the code is the one you provided. Following this, I get for example that the value 1 occurs 19 times, value 2 occurs 17, value 3 15 times, value 4 25 times etc.

Is there any way to get an equal number of occurrences? Of course, one of the values will be +1 since now the end array is odd-sized.

[Mikel Jimenez]

Hi Voss, I've found this code that works fine for the shuffling without consecutive numbers, but still the occurrences of each number are not equal:

n=103;
k=6;
t=1;
allPos=1+mod(cumsum)[randi(k,t,1),randi(k-1,t,n-1)],2),k);

Invalid expression. When calling a function or indexing a variable, use parentheses. Otherwise, check for mismatched delimiters.

[Voss]

Doesn't seem like that code runs at all.

[Mikel Jimenez]

Might have a typo. Now this below is working perfectly, with the same number of occurrences for each value. I get a 104 size vector instead of 103, but that's the best I can get I guess. Thanks

n=6;
k=18;
d=42; %// random number to fail first check
while(~all(sum(bsxfun(@eq,d,(1:n).'),2)==k)) %' //Check all numbers to appear k times.
    d=mod(cumsum([randi(n,1,1),randi(n-1,1,(n*k)-1)]),n)+1; %generate new random sample, enforcing a difference of at least 1.
end

[Voss]

If that gives you 104 elements, just remove the first or last element afterwards:

d(end) = []; % for example

Answer 2

[David Hill]

leftSides = [1,3,5];
leftPos_trials = repmat(leftSides,1,14);
idx=randperm(42);
while any(diff(leftPos_trials(idx))==0)
    idx=randperm(42);%try until you get one to work
end
leftPos_trials(idx)

ans = 1×42

3 5 3 5 3 5 1 3 1 5 1 5 3 1 5 3 1 5 1 3 5 1 3 1 5 3 1 5 3 1

[Torsten]

@David Hill

According to the question, the shuffling should be applied to the vector "leftSideProbes_random" and not to the vector "leftPos_trials". But maybe it was a mistake from the OP's side.

[Mikel Jimenez]

Hi David,

This works great. However, it takes ages (about 20 secs) to get through the while loop (or is it just on my computer?).

UnfortunateIy I cannot introduce this delay in my code, would you know any other way to get the same results without the delay?

Thanks.

[Voss]

@Mikel Jimenez: See if my answer works for you:

https://www.mathworks.com/matlabcentral/answers/1905476-randomize-vector-avoiding-consecutive-values#answer_1162601

Answer 3

[John D'Errico]

Typically, rejection would be necessary. Of course, if your initial vector were composed only of two elements, then there are only two possible "random" configurations that lack any direct repeats, thus the sequence

01010101010101010101...

or

10101010101010101010...

In your case, it is not too much better. You want random sequences of 3 elements where no element appears consecutively. Again, rejection would seem to be the solution. But an alternative is not too difficult to build that does not involve rejection. The advantage is if you have a long sequence, rejection will often be almost impossible to use, since some repeats will almost always happen, and then rejection would just have you start over again.

Anyway, the function randwithoutreps will suffice. It does not use rejection at all. It could probably be written in a better way, but there is no real need for that. One should never spend time to improve efficient code.

randwithoutreps(5)

ans = 1×15

1 3 1 3 2 3 1 2 3 2 1 2 1 3 2

It is reasonably fast.

timeit(@() randwithoutreps(1000))

ans = 0.0378

So a fraction of a second to generate a sequence as desired with length 3000 elements. If you tried to solve that using rejection, you would be waiting for years probably until you got lucky enough.

any(0==diff(randwithoutreps(10000)))

ans = logical
   0

So a sequence of length 30000 elements. As you can see, there were no repeated elements.

hist(randwithoutreps(1000))

And each element appeared exactly 1000 times.

If you wanted some other elements, then just use the result as an index into another vector.

V = [2 3 5];
V(randwithoutreps(5))

ans = 1×15

5 3 5 2 5 3 5 3 2 3 2 5 2 3 2

The code is pretty simple.

function vec = randwithoutreps(reps)
  % generate a random sequence of elements from the set [1 2 3] with no repeats
  % usage: vec = randwithoutreps(reps)
  %  reps the number of times each element will appear
  
  vec = zeros(1,3*reps);
  
  % choose in advance where to locate the 1 elements first, so there are
  % no repeated ones. This means we must ALWAYS have at least one other
  % element between each pair of ones.
  locs1 = 1:3*reps;
  for i = 1:reps
    % choose any element randomly from the vector locs
    loc = randi(numel(locs1));
    loc = locs1(loc);
    vec(loc) = 1;
    locs1 = setdiff(locs1,loc + [-1 0 1]);
  end
  
  % next, find all sequences composed of purely zeros that remain in vec
  % each such sequence MUST be filled with either the sequence [2 3 2 3 ...]
  % or the sequence [3 2 3 2 ...]. These are the only possibilities we
  % can allow.
  remain23 = [reps,reps];
  zeroblocks = [strfind([1,vec],[1 0]);strfind([vec,1],[0 1])];
  
  for i = 1:size(zeroblocks,2)
    blocklen = diff(zeroblocks);
    [blocklen,ind] = max(blocklen);
    blocklen = blocklen + 1;
    
    % we need to choose between the subsequences [2 3 2 3...] and [3 2 3 2...]
    if mod(blocklen,2) == 0
      r = rand > 0.5;
      subseq = 2 + mod(r + (1:blocklen),2);
      remain23 = remain23 - blocklen/2;
    else
      r = diff(remain23) < 0;
      subseq = 2 + mod(r + (1:blocklen),2);
      remain23 = remain23 - floor(blocklen/2);
      remain23(2 - r) = remain23(2 - r) - 1;
    end
    
    vec(zeroblocks(1,ind):zeroblocks(2,ind)) = subseq;
    
    zeroblocks(:,ind) = [];
  end
end

[Mikel Jimenez]

Thanks a lot for your thorought answer, John. This seems to be doing the trick perfectly too (all three answers seems to work, actually), yet I was hoping for a shorter code.

[John D'Errico]

This is a non-trivial problem to solve, as evidenced by the non-trivial solutions you have been given. By your requirement of non-consecutive elements, That forces the "random" set to be not fully random. Still random in a sense, but strongly non-random in other ways.

[Mikel Jimenez]

I've found this code that works fine for the shuffling without consecutive numbers, but still the occurrences of each number are not equal:

n=103;
k=6;
t=1;
allPos=1+mod(cumsum)[randi(k,t,1),randi(k-1,t,n-1)],2),k);

I thought this was going to be easier to achieve...