Zeros and ones vector

31 次查看(过去 30 天)
Fieke Schram
Fieke Schram 2021-5-19
评论: Adam Danz 2021-5-20
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;
  1 个评论
Rik
Rik 2021-5-19
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.

请先登录,再进行评论。

回答(4 个)

DGM
DGM 2021-5-19
编辑:DGM 2021-5-20
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
Adam Danz 2021-5-19
编辑:Adam Danz 2021-5-19
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
permsetDir = 200×8
0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1
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
permsetDir = 200×8
1 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0 0 1 0 0
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)
  1 个评论
Image Analyst
Image Analyst 2021-5-20
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
David Goodmanson 2021-5-19
编辑:David Goodmanson 2021-5-20
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
  5 个评论
Adam Danz
Adam Danz 2021-5-20
Nice update, David!

请先登录,再进行评论。


Image Analyst
Image Analyst 2021-5-20
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.
  1 个评论
Adam Danz
Adam Danz 2021-5-20
I think the OP meant consecutively. Their example contains 8 elements per row and each row should have the same number of 1s and 0s meaning four 1s and four 0s. There can't be only three of the same value per row if the only options are 0 and 1 and the number of 0s and 1s should be equal.

请先登录,再进行评论。

类别

Help CenterFile Exchange 中查找有关 Multirate Signal Processing 的更多信息

Community Treasure Hunt

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

Start Hunting!

Translated by