How do I create a set of 20 random binary numbers (only 0 and 1) but such that 0 or 1 does not repeat 4 times in a row?

How do I create a set of 20 random binary numbers (only 0 and 1) but such that 0 or 1 does not repeat 4 times in a row?

for example the set should not have ( 0 , 0, 1, 0, 1,1,1,1) because I dont want 4 of the same number in a row since 1 repeats 4 times

Answer 1

[Walter Roberson]

Create a set of random binary numbers. Test whether it has the required properties. If it does, accept it; otherwise loop back and generate another set.

[moizz]

Thank you for your help but how would i create the script to get it the first time, because the probability of getting a set in which 4 numbers repeat is quite high?

[Walter Roberson]

rand(1,20)>0.5 and then test it to see if it passes or not. You will probably have to iterate a few times.

[Sean de Wolski]

This doesn't scale well...

for ii = 1:100
  x = rand(1,100)>0.5;
  idxZ = strfind(x,[0 0 0 0]);
  idx1 = strfind(x,[1 1 1 1]);
  if isempty(idxZ)&&isempty(idx1)
      break
  end
end

[Sean de Wolski]

Interesting to see how long it takes:

First 10x

 8758        7213        1214         299        3314         362
       2095        1773         122        1798

[Walter Roberson]

It doesn't have to scale well; if larger matrices had been indicated then I would have given different code. The problem with Order Analysis is that it is for the asymptoptic case and ignores that at low orders there might be more efficient code.

Answer 2

[Jonathan Epperl]

Create them step-by-step, and if you have 3 0 or 1 in a row, force a 1 or 0 for the next. What I mean:

rbits = false(1,20);
rbits(1:3) = rand(3,1)>.5; % The first 3 can be whatever
for k=4:20
     rbits(k) = ~all(rbits(k-3:k-1)) & ( all(~rbits(k-3:k-1)) | rand()>.5);
end
rbits

I am fairly certain that is equivalent to just filling the vector randomly and then changing the forth 1 to a zero, the 4th zero to a 1:

rbits = rand(1,20)>.5
rbits_old = ~rbits
while any(rbits~=rbits_old)
  rbits_old = rbits;
  RB = [rbits'  circshift(rbits',1 ) circshift(rbits',2) circshift(rbits',3)]';
  rbits(all(RB,1)) = 0
  rbits(all(~RB,1)) = 1
end

I am not 100% certain about the second syntax and whether it could get you into an infinite loop, but if your number of random bits was much more than 20, a syntax along the lines of the second suggestion should be faster.

[moizz]

Thank You very much, also how would I be able to add to this script such that there are equal amount of 1 and 0, So for example there will always be ten 1 and ten 0.

[Jonathan Epperl]

Jeez, that is way easier, why didn't you say so from the start ;-)

% 10 ones, 10 zeros
p = [true(1,10) false(1,10)];
% permute them randomly
rbits = p(randperm(20));
RB = [rbits' circshift(rbits',1 ) circshift(rbits',2) circshift(rbits',3)]';
% Now check whether your requirements are satisfied
while any(all(RB)|all(~RB))
  % If they are, you won't get in here, if they ain't, then try another 
  % permutation
  rbits = p(randperm(20));
  RB = [rbits' circshift(rbits',1 ) circshift(rbits',2), circshift(rbits',3)]';
end
rbits

Answer 3

[Azzi Abdelmalek]

x=zeros(1,20)
x(1:10)=1
y=x(randperm(20))
c1=3:4:20
y(c1+1)=not(y(c1))

[Azzi Abdelmalek]

don't work with c1=3:4:20 (c1=3:3:20 is correct)

corrected code

x=zeros(1,20)
x(1:10)=1
y=x(randperm(20))
c1=3:3:20
y(c1+1)=not(y(c1))

Answer 4

[Sean de Wolski]

How about:

x = [0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 0]; %to test it
x = strrep(x,[0 0 0 0],[0 0 1 0]);
x = strrep(x,[1 1 1 1],[1 1 0 1]);

In general, x would just be:

x = rand(sz)>0.5;

Answer 5

[Andrei Bobrov]

a = randi([0 1],1,20);
p = conv(a,[1 1 1 1],'same');
a(p == 4) = 0;
a(p == 0) = 1;

add

a = ones(1,20);
a(randi(4,1,5) + 4*(0:4)) = 0;
a(conv(a,[1 1 1 1],'same') == 4) = 0;

or

ii = randi(3,1,20);
ii = ii(1:find(cumsum(ii) >= 20,1,'first'));
out1 = cell(size(ii));
out1(1:2:end) = arrayfun(@(x)ones(1,x),ii(1:2:end),'un',0);
out1(2:2:end) = arrayfun(@(x)zeros(1,x),ii(2:2:end),'un',0);
out = cell2mat(out1);
out = out(1:20);

[Sean de Wolski]

This doesn't work for cases when there are many zeros or ones in a row:

a = zeros(1,20)

[Andrei Bobrov]

add

Answer 6

[Matt Fig]

Some methods proposed here don't seem to generate 'random' vectors. Here is an approach that is perhaps 'more random' than some, yet faster than Walter's brute force (especially for larger vectors). As all of the functions called are built-ins, it works pretty fast....

X = rand(1,10000)>.5;
S = {strfind(X,[1 1 1 1]),strfind(X,[0 0 0 0])};

while ~all(cellfun('isempty',S))

      for ii = 0:1    
          for jj = 1:length(S{ii+1})
              X(S{ii+1}(jj) + randperm(4,1)-1) = ii;
          end
      end

      S = {strfind(X,[1 1 1 1]),strfind(X,[0 0 0 0])};
end