7 views (last 30 days)

Show older comments

How can I make a semi randomised vector with the same amount of zeros and ones that does not have more than three ones or zeros in a row?

permset = zeros(200,4);

permsetDir = [permset permset];

[m,n]=size(permset);

Dir = [0 0 0 0 1 1 1 1];

for i=1:m;

permsetDir(i,:)=Dir(1,randperm(2*n));

end;

Rik
on 19 May 2021

The easy way is to just generate an array with random values, mark every value below the median as 0 and the rest 1. Then you can reject it if it doesn't fit the requirement.

That might take very long for larger vectors.

DGM
on 19 May 2021

Edited: DGM
on 20 May 2021

I don't know of a nice way to do this, and I'm not known for being clever or elegant, so take this with a grain of salt.

Depending on how loosely we interpret "random", and how overcomplicated a solution is acceptable, the following may work.

clc; clearvars

N = 1000; % length of vector

maxb = 3; % maximum block size

% generate lists of runlengths

N = round(N/2)*2; % N must be even

notclose = true;

while notclose

orunl = getrunl(maxb,N);

zrunl = getrunl(maxb,N);

% the interleaving requires this restriction to guarantee

% we don't violate blocksize constraint at the ends

len = [numel(orunl) numel(zrunl)];

if abs(diff(len))<=1

notclose = false;

end

end

% generate blocks of ones and zeros

Co = mat2cell(ones(N/2,1),orunl,1);

Cz = mat2cell(zeros(N/2,1),zrunl,1);

len = [numel(orunl) numel(zrunl)]

% interleave the blocks

if diff(len)==0

C = reshape([Co Cz].',[],1);

elseif len(1)>len(2)

C = reshape([Co(1:end-1) Cz].',[],1);

C = [C; Co(end)];

elseif len(2)>len(1)

C = reshape([Cz(1:end-1) Co].',[],1);

C = [C; Cz(end)];

end

out = vertcat(C{:}); % <--- this is the result

function thisrunl = getrunl(maxb,N)

runl = randi(maxb,N/2,1);

idx = find((cumsum(runl)-N/2)<0.1,1,'last');

thisrunl = runl(1:idx);

s = sum(thisrunl);

if s < N/2

thisrunl = [thisrunl; N/2-s];

end

end

The last part using cell arrays to assemble the vector could be replaced with a loop that builds the output directly from the runlength lists, but this method is more general, allowing interleaving of numbers from two different sets using constrained chunk sizes. That's (similar to) what this code was originally intended to do, and why it ends up being such a ridiculously overcomplicated way of doing it.

At the very least, this method (or something similar) tends to be much faster than rejecting the entire vector. It can assemble a 1E6-element vector in about as much time as blind trial and error can assemble a 200-element vector, and the penalty for vector length doesn't scale as unfavorably, either.

EDIT:

Instead of a loop, this would work in place of the cell array manipulation.

runl = zeros(sum(len),1);

if diff(len)==0

runl(1:2:end-1) = orunl;

runl(2:2:end) = zrunl;

out = repelem(mod(0:sum(len)-1,2),runl);

elseif len(1)>len(2)

runl(1:2:end) = orunl;

runl(2:2:end-1) = zrunl;

out = repelem(mod(1:sum(len),2),runl);

elseif len(2)>len(1)

runl(1:2:end) = zrunl;

runl(2:2:end-1) = orunl;

out = repelem(mod(0:sum(len)-1,2),runl);

end

out % <--- this is the result

Typical exec times using this simplification are about 5ms for 1E3 elements or 2.5s for 1E6 elements.

The next target for optimization would be the first while loop. For large vector sizes, the cost of rejecting runl vectors because their lengths differ too much is high. Most variability in execution time comes from this waste. The restriction imposed by the exit condition is not strictly required, but if the lengths differ by more than 1, then it's implied that some runs must be concatenated. In order to allow greater differences in vector lengths, they must be tested and conditionally arranged during interleaving such that they don't violate the maxb constraint. For larger maxb, there's likely a decent payoff for the extra complication, but for maxb=3, I figured it's not worth the extra confusion.

EDIT AGAIN:

I read the problem description quite literally:

a semi randomised vector with the same amount of zeros and ones that does not have more than three ones or zeros in a row

Since the sentence describes a vector, it's implied that "in a row" means "consecutively". If I solved the wrong problem, then well. I guess that's why.

Adam Danz
on 19 May 2021

Edited: Adam Danz
on 19 May 2021

Here are two methods. The first is fast and simple. The second does not require writing loops and has less lines but is very slow and is for demo purposes only.

Both methods are as random as possible given the constraint of avoiding 4 or more consecutive values per row.

Simple & fast loop (<0.001 sec)

This method starts by randomly permuting the vector [1 1 1 1 0 0 0 0] and then iteratively testing whether there are 4 consectuve values (1s or 0s) and if so, another random permutation is attempted until the test passes, for each row of the matrix.

rng('default') % For reproducibility

nRows = 200; % number of rows to create

base = [1 1 1 1 0 0 0 0];

nBase = numel(base);

permsetDir = zeros(nRows, numel(base));

% Loop through each row

for i = 1:nRows

pass = false;

while ~pass

permsetDir(i,:) = base(randperm(nBase));

% Count number of consecutive 1s and 0s in row i

oneCt = diff(find([0,permsetDir(i,:),0]==0))-1;

zeroCt = diff(find([1,permsetDir(i,:),1]==1))-1;

% If there are not more than 3 consecutive values, go to next row

if max([oneCt,zeroCt])<=3

pass = true;

end

end

end

Show result

permsetDir

Loop-less version (40 seconds)

Well.. the loops are hidden at least.... but it's nearly unreadable and very slow ðŸ‘Ž.

This starts by producing every permutation of [1 1 1 1 0 0 0 0] and then eliminates rows with 4 consecutive values resulting in a 35712x8 matrix of all leftover permutations. Then permsetDir is generated by randomly selecting 200 rows the permutation matrix. Note that you could select 200 unique rows using randsamp or randperm but there won't be 200 unique rows in the final matrix since there are only 2 unique values in the vector.

rng('default') % For reproducibility

nRows = 200; % number of rows to create

tic

base = [1 1 1 1 0 0 0 0];

basePerms = perms(base);

% eliminate rows with 4 consecutive values

onevec = ones(size(basePerms,1),1);

[rowNum0,colNum0] = find([onevec, basePerms, onevec]==1);

rmIdx0 = arrayfun(@(r)max(diff(colNum0(rowNum0==r))-1),1:size(basePerms,1)) >= 4;

[rowNum1,colNum1] = find([onevec-1, basePerms, onevec-1]==0);

rmIdx1 = arrayfun(@(r)max(diff(colNum1(rowNum1==r))-1),1:size(basePerms,1)) >= 4;

basePerms(rmIdx0 | rmIdx1,:) = [];

% randomly select nRows of the permuted matrix

randSelection = randi(size(basePerms,1),nRows,1);

permsetDir = basePerms(randSelection,:);

Show result

permsetDir

You can confirm that the output matrix has an equal number of 1s and 0s in each row with this test which should return true:

all(mean(permsetDir,2)==.5)

Image Analyst
on 20 May 2021

He wanted a matrix "that does not have more than three ones or zeros in a row". Your rows have 4 ones and 4 zeros in each row. Note he said "in a row", not "consecutively" -- there is a difference, though it could just be a case of ambiguous, imprecise, sloppy wording on the poster's part.

So for the 4 column matrix he wanted, I'd just make a matrix of all zeros and scan down row by row using randi(3, 1) to get a number anywhere from 1 to 3, then use that number in randperm() to get the location of those ones, and then assign them.

David Goodmanson
on 19 May 2021

Edited: David Goodmanson
on 20 May 2021

Hi Fieke,

My previous effort answered the wrong question (the code for that is under the dashed line below).

You want a matrix of rows where each row fits the criterea and the rows are considered independently, i.e. if a row ends in 1 1 and the next row starts with 1 1 , that is all right.

The matrix S below has 62 rows containing all possible solutions for rows of length n = 8. Then you can pick rows at random to make up the final matrix as on the last line.

The code is generalizable for rows of even length n (within reason).

% all possible solutions of length n with n/2 zeros, n/2 ones,

% no more than three zeros or three ones 'in a row'

n = 8;

% S contains all possible n-bit sequences, one per column;

% then reduce to n/2 zeros, n/2 ones

S = (abs(dec2bin((0:2^n-1)'))-48)';

S = S(:,sum(S)==n/2);

% eliminate columns with more than three zeros or three ones 'in a row'

ind = any(diff(S,3) ==0 & diff(S(1:end-2,:)) ==0);

S(:,ind) = [];

S = S'; % each row is a solution

nrow = size(S,1);

M = S(randi(nrow,211,1),:)

% -----------------------------------------------------------------------------------------------

This code creates a long vector that contains no more than three ones in a row and no more than three zeros in a row. Do this by concatenating random four-bit sequences, and avoiding sequences that would result in too many zeros or ones in a row. Does NOT produce equal numbers of zeros and ones. For a vector of length 4 million, it takes about half a second.

N = 1e5; % the length of the result vector is 4*N

% S contains all four-bit sequences with no more than three 0's or 1's in a row

S = (abs(dec2bin((1:14)'))-48)'

% make an index vector to columns of S

a = zeros(1,N);

a(1) = randi(14);

for k = 2:N

b = a(k-1);

if rem(b,4) == 1

a(k) = randi(13);

elseif rem(b,4) == 2

a(k) = randi(13)+1;

elseif rem(b,8) == 3

a(k) = randi(11);

elseif rem(b,4) == 4

a(k) = randi(11)+3;

elseif b == 7

a(k) = randi(7);

else a(k) = randi(7)+7; % b == 8

end

end

R = S(:,a); % apply index vector

R = R(:); % the result is a column vector; use R = R(:)' for a row vector

Image Analyst
on 20 May 2021

He wanted a matrix "that does not have more than three ones or zeros in a row". Your rows have 4 ones and 4 zeros in each row. Note he said "in a row", not "consecutively" -- there is a difference, though it could just be a case of ambiguous, imprecise, sloppy wording on the poster's part.

So for the 4 column matrix he wanted, I'd just make a matrix of all zeros and scan down row by row using randi(3, 1) to get a number anywhere from 1 to 3, then use that number in randperm() to get the location of those ones, and then assign them.

So, try this:

% First define as all zeros. 200 rows and 4 columns.

m = zeros(200, 4)

% Go down row-by-row, assigning a random number

% of ones to random locations.

for row = 1 : size(m, 1)

% Get the number of ones in this row.

numberOf1s = randi(3)

% Get the location of the ones.

columns = randperm(4, numberOf1s)

% Assign the 1s to those locations.

m(row, columns) = 1;

end

m % Show in command window.

% You'll find no more than three ones in a row.

Adam Danz
on 20 May 2021

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!