1

I want to make an array called result, which has dimensions (14,12,10) and has values random[0 2], but it should not contain 0 more than three consecutive times in each row (dimension 2), and the sum of all values in each row must be <= 11.

This is my current approach:

jum_kel = 14;
jum_bag = 12;
uk_pop = 10;

for ii = 1:uk_pop,
  libur(:,:,ii) = randint(jum_kel,jum_bag,[0 2]); %#initialis
  sum_libur(1,:,ii) = sum(libur(:,:,ii),2); %#sum each row
end

for jj = 1:jum_kel
  while sum_libur(1,jj,ii) > 11, %# first constraint : sum each row should be <=11,
    libur(jj,:,ii) = randint(1,jum_bag,[0 2])
    sum_libur(1,:,ii)=  sum(libur(:,:,ii),2);
    for kk = 1:jum_bag
      if kk>2
        o = libur(jj,kk,ii)+libur(jj,kk-1,ii)+libur(jj,kk-2)
        while kk>2 && o==0 %# constraint 2: to make matrix will not contain consecutive triplets (0-0-0) in any row.
          libur(jj,:,ii) = randint(1,jum_bag,[0 2]); 
          sum_libur(1,:,ii)=  sum(libur(:,:,ii),2);
        end
      end
    end
  end
end

but this is extremely slow...Does anyone see a faster method?

AGS
  • 14,288
  • 5
  • 52
  • 67
Febri Dwi Laksono
  • 309
  • 1
  • 7
  • 15

3 Answers3

2

(sidenote: A matrix does not have 3 dimensions: that would be a tensor, in which case the concept of "row" is not well-defined.)

The easiest way is to use Rejection Sampling. Normally this might be slow, and even though you don't mention it, I'd worry this code might occur in a performance-critical section of your program. Nevertheless, everything is okay, since the chance of a 14 3-sided coinflips in a row containing the substring 0-0-0 is fairly small. Even it's an issue, since the matrix is (supposedly) uniformly distributed, its elements must also be independently distributed, so you can sample each row separately, rejecting and recreating any row with 0-0-0 in a row or which has a sum <= 11.

ninjagecko
  • 88,546
  • 24
  • 137
  • 145
  • sorry, i'am newbie in matlab user. so i difficult to make code with it. can you help me please? if you dont mind. – Febri Dwi Laksono Aug 17 '12 at 06:08
  • @FebriDwiLaksono: Start with a uniformly random NxM matrix, then make a for loop that checks row1,row2,row3,... For each row, go into a while loop: as long as that row violates any of your constraints, recreate that row (by creating a new uniformly random 1xM matrix) and replacing the rows with that new matrix. – ninjagecko Aug 17 '12 at 06:11
  • @FebriDwiLaksono: The method I suggested is very fast and only has a while loop in a for loop. The method you have seems to have many nested loops. I cannot understand the code and why you have multiple sets of matrices and how they relate to each other, but the above method should work quickly. – ninjagecko Aug 17 '12 at 07:14
  • yeah thanks youu mr. ninjagecko. i just cannot make a code. i mean translate my logica to matlab languange because i'am newbie. – Febri Dwi Laksono Aug 17 '12 at 07:49
0

As indicated by @ninjagecko, rejecting and recreating is the most obvious (if not the only) way to go here. In that light, I think this'll do nicely: 

R = 14;
C = 12;
T = 10;

result = zeros(C,R*T);

for ii = 1:(R*T)
    done = false;
    while ~done
        newRow = randi([0 2],C,1);
        done = ...
            (sum(newRow)<12) && ...
            (~any(diff([0;find(newRow);C+1])>3));
    end
    result(:,ii) = newRow;
end

result = permute(reshape(result,C,R,T), [2 1 3]);

Note that <12 equals <=11 for integer math (and >3 equals >=4), but requires one less check and is thus faster. The variable newRow is created as a column vector, since such things are better organized in memory and can be checked faster. 3D arrays are generally slower to assign to than 2D matrices, therefore everything is kept 2D until after all operations. The most computationally intense check (~any(diff(find(newRow))>3)) is done last, so that short-circuiting (&&) may render its evaluation unnecessary. Both loops are small and fulfil all conditions to be compiled to machine code by Matlab's JIT.

So this is pretty close to optimized, and will be pretty fast. Unless someone comes up with an entirely different algorithm for this, I believe this is pretty close to the theoretical maximum speed in Matlab. If you need to go faster, you'll have to switch to C (which will allow optimization of the constraint checks).

Rody Oldenhuis
  • 37,726
  • 7
  • 50
  • 96
  • There -- I optimized it further. Are the 12,14 and 10 the actual sizes, or are they larger for your case? I assumed the latter, hence all the speed-related optimizations... – Rody Oldenhuis Aug 17 '12 at 08:08
  • Hmmm...strangely enough the triple-loop solution I had earlier is equally fast, if not faster...Interesting :) – Rody Oldenhuis Aug 17 '12 at 08:15
  • until now, i just use that actual size. maybe if I have larger size, i will ask you again ahaha. your code is related with rejection sampling or not mr? – Febri Dwi Laksono Aug 17 '12 at 08:28
  • Mr, Why Do i still find value "0" more than three times in any row. when I run and then I check the matrix "result", the result contain value zeros which appears more than three times in a row like [0-0-0-0-0]. – Febri Dwi Laksono Aug 17 '12 at 08:41
  • the update one mr. but before when I used the old one, it also still contain like that. – Febri Dwi Laksono Aug 17 '12 at 08:50
  • Ah, I had forgotten a boundary case. This should fix it. – Rody Oldenhuis Aug 17 '12 at 08:57
  • Oldenhius: boundary case?? what did you mean? – Febri Dwi Laksono Aug 17 '12 at 08:59
  • Oldenhius: Why still have contain consecutive zeros more than 3 yeah Mr. but with boundary case that you give make result better than code before. but still have.. – Febri Dwi Laksono Aug 17 '12 at 09:03
  • The original condition only checked for `[...,0,0,0,...]` This would miss `[...,0,0,0]` or `[0,0,0,...]`. Come to think of it...I've only fixed the last case now :). I'll update again in 5 minutes. – Rody Oldenhuis Aug 17 '12 at 09:03
  • There. If you have any more problems, let me know. – Rody Oldenhuis Aug 17 '12 at 09:09
  • i think your last updated code is right, thanks you so much Mr. Rody. you are very kind. ouh yeah I add your facebook Id already. so that if I have problem, i will be easy to tell you. hehe dont you mind right? – Febri Dwi Laksono Aug 17 '12 at 09:48
  • @RodyOldenhuis: that < is faster than <= seems dubious, and the translation makes for less-readable code. It is very likely that any low-level programming language (like Matlab's numerical operations), or high-level language which compiles smartly to low-level machine code, does the instruction in one clock cycle (or at the very least rewrites it as the faster check). http://stackoverflow.com/questions/1029992/is-the-inequality-operator-faster-than-the-equality-operator – ninjagecko Aug 17 '12 at 15:23
  • Can you provide some test results to back that up? – Rody Oldenhuis Aug 17 '12 at 15:29
  • @RodyOldenhuis: can you provide some test results to back your claim up? =) – ninjagecko Aug 17 '12 at 16:07
  • @nijagecko When you make a counterclaim, the burden of evidence is not on *my* side :) – Rody Oldenhuis Aug 17 '12 at 16:32
  • @ninjagecko But, here you go: executing `tic, for ii = 1:1e7; rand < rand; end; toc` both for `<` and `<=` consistently gives faster times for `<`. (Matlab R2010b, Ubuntu 12.10 64bit, linux 3.0.0-23, AMD Phenom II X6 1100T) – Rody Oldenhuis Aug 17 '12 at 18:11
  • @ninjagecko **Slightly** faster though :) – Rody Oldenhuis Aug 17 '12 at 20:00
0

For simply finding a series of numbers in an array, you can (ab)use strfind. When indexing into a multidimensional array, you can also combine subindices and linear indexing to the remaining dimensions (used in the assignment result(:,ii) = newRow):

result = NaN(12,14,10);
for ii = 1:14*10
    while 1
        newRow = randi([0 2],12,1);
        if isempty(strfind(newRow',[0 0 0])) && sum(newRow)<=11
            result(:,ii) = newRow; 
            break;
        end
    end
end
result = permute(result, [2 1 3]);
Gunther Struyf
  • 11,158
  • 2
  • 34
  • 58