7

I'd like to create a Matrix in MATLAB where:

The First row consists of a random arrangement of 0s and 1s, split evenly (i.e. 50-50).

The Second row randomly assigns zeros to 50% of the 0s and 1s in the first row, and ones to the remaining 50%.

The Third row randomly assigns zeros to 50% of the 0s and 1s in the second row, and ones to the remaining 50%.

Non-randomized Example:

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1  
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1  
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Any suggestions?

Adriaan
  • 17,741
  • 7
  • 42
  • 75
BenJHC
  • 89
  • 6
  • Is that not the same as just shuffling the columns of your non-randomized example? If so, just use `randperm` – Dan Nov 10 '15 at 12:55
  • 2
    @Dan: Don't think so, by chance the third row could look like the first if I understand the description right. Permuting, you can't achieve this. – Daniel Nov 10 '15 at 12:58

4 Answers4

7

A solution based on checking whether numbers are bigger or smaller than the median. As long as the number of columns tested is even, exactly half of a set of random doubles will be bigger than the median, and half will be smaller. This guarantees that there's exactly 50% of bits get flipped. 

nRows = 3;
nCols = 16; %# divisible by 4

%# seed the array
%# assume that the numbers in each row are unique (very, very likely)
array = rand(nRows,nCols); 


out = false(nRows,nCols);

%# first row is special
out(1,:) = array(1,:) > median(array(1,:));

%# for the rest of the row, check median for the zeros/ones in the previous row
for iRow = 2:nRows
    zeroIdx = out(iRow-1,:) == 0;
    %# > or < do not matter, both will replace zeros/ones 
    %# and replace with exactly half zeros and half ones
    out(iRow,zeroIdx) = array(iRow,zeroIdx) > median(array(iRow,zeroIdx));
    out(iRow,~zeroIdx) = array(iRow,~zeroIdx) > median(array(iRow,~zeroIdx));
end
Jonas
  • 74,690
  • 10
  • 137
  • 177
3

I'd offer a short bsxfun solution:

%// number of divisions
n = 4;

%// unshuffled matrix like in your example
unshuffled = bsxfun(@(a,b) mod(a,2*b) > b-1, meshgrid(1:n^2,1:n) - 1, (2.^((n-1):-1:0)).') %'

%// shuffle columns
shuffled = unshuffled(:,randperm(n^2))

unshuffled =

 0     0     0     0     0     0     0     0     1     1     1     1     1     1     1     1
 0     0     0     0     1     1     1     1     0     0     0     0     1     1     1     1
 0     0     1     1     0     0     1     1     0     0     1     1     0     0     1     1
 0     1     0     1     0     1     0     1     0     1     0     1     0     1     0     1


shuffled =

 1     0     1     1     0     1     0     1     1     1     1     0     0     0     0     0
 1     1     1     0     0     1     1     0     1     0     0     0     1     0     1     0
 1     0     0     1     0     0     0     0     1     1     0     1     1     0     1     1
 1     1     1     1     0     0     0     0     0     0     1     0     0     1     1     1

First you need to create the unshuffled matrix, which can be done by comparing the matrix generated by meshgrid(1:n^2,1:n) with a row dependent modulus. Finally you just need to shuffle the columns.

Robert Seifert
  • 25,078
  • 11
  • 68
  • 113
  • 1
    As pointed out in the comments to the question, shuffling the columns of the perfect non-randomized matrix might not be enough. As the question is phrased, granted that it is not phrased well, there is no reason why there couldn't be 2 columns of only `1`s for example. This method effectively considers all the previous rows at each step and not just the immediately previous row. – Dan Nov 10 '15 at 14:40
  • @Dan No matter how I twist my mind, I can't interpret the question this way. We have to wait for the OP I guess. – Robert Seifert Nov 10 '15 at 14:50
  • OP states "The Third row randomly assigns zeros to 50% of the 0s and 1s in the **second** row, and ones to the remaining 50%.", so the third row need not consider the first row at all and thus could in fact be identical to the first row... – Dan Nov 10 '15 at 14:57
3

If you have the Statistics Toolbox, you can do it very easily with randsample:

M = 3; %// number of rows
N = 16; %// number of columns. Should be multiple of 4, according to problem definition 
result = zeros(M,N); %// preallocate and initiallize to zeros
result(1, randsample(1:N,N/2)) = 1; %// first row: half values set to one, half to zero
for m = 2:M
    result(m, :) = result(m-1, :); %// initiallize row m equal to row m-1
    result(m, randsample(find(result(m-1,:)), N/4)) = 0; %// change half of ones
    result(m, randsample(find(~result(m-1,:)), N/4)) = 1; %// change half of zeros
end

Example result:

result = 
     0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1
     1 1 0 0 0 1 1 1 0 1 0 1 0 0 0 1
     1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1
Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
  • I don't think this is correct. My understanding is that for the 8 `1`s in row 2, exactly 4 of the corresponding elements of row 3 should be `1`. In your sample `result` only 2 are `1` – Dan Nov 11 '15 at 06:13
  • 1
    @Dan Thanks for pointing it out. There was a line missing to initiallize each row to the previous one. Corrected! – Luis Mendo Nov 11 '15 at 07:22
2

A solution using randperm:

nrows = 3;
ncols = 16;
M = zeros(nrows,ncols);    

%// seed the first row
M(1,1:ncols/2) = 1;
M(1,:) = M(1,randperm(ncols));

for r = 2:nrows

    %// Find ncols/4 random between 1 and ncols/2. These will be used to index half of the previous rows 1 elements and set them to one
    idx = randperm(ncols/2);
    idx1 =  idx(1:ncols/4);
    %// Do the same thing again, but this time it will be used for the 0 elements of the previous row
    idx = randperm(ncols/2);
    idx0 =  idx(1:ncols/4);

    idx_prev1 = find(M(r-1,:)); %// Find where the 1 elements were in the last row
    idx_prev0 = find(~M(r-1,:)); %// Find where the 0 elements were in the last row   

    M(r,idx_prev1(idx1))=1; %// Set half of the previous rows 1 elements in this row to 1
    M(r,idx_prev0(idx0))=1; %// Set half of the previous rows 0 elements in this row to 1

end
Dan
  • 45,079
  • 17
  • 88
  • 157