Faster way for all possible arrangements

currently my .m file looks like this

 for a = 1 : 47
  for b = a+1 : 48
   for c = b+1 : 49
    for d = c+1 : 50
     fprintf('%d %d %d %d \n',a,b,c,d);
    end
   end
  end

I am trying to generate sets of 4 elements from 1,2,3,...50 i.e. {1,2,3,4},{1,2,3,5},...{1,2,3,50},{1,2,4,5},..{47, 48, 49, 50}. Hence, in total there are C(50,4) sets. I would like to know whether there are any faster alternatives than these 4 nested loops? The order in one set does not necessarily in increasing order. i.e. it is ok if the code generate {4,1,2,3} rather than {1,2,3,4}.

Answer 1

[Jan]

FEX: vchoosek:

q = vchoosek(1:50, 4);

This needs 0.015 sec under Matlab 2009a/64. Matlab's nchoosek needs 0.9 sec.

If the order matters, this means if you want to get {1,2,3,4} and {1,3,2,4} etc, use FEX: vchooseko.

[endeavour90]

Is there a way to generate the sets row by row instead of storing all the combination first in a matrix? I am afraid that I also need to generate combination of 7 elements from 50 elements

[Jan]

The posted function works for UINT8 values also, which need 1 byte per element compared to 8 for DOUBLEs:

q = vchoosek(uint8(1:50), 7)

Answer 2

[Daniel Shub]

I think the fullfact function from the stats toolbox gets you close.

x = fullfact([50,50,50,50]);

Although you seem to be preventing sequences with repeats so you will need to find those after the fact.

Answer 3

[Richard Brown]

What you are currently doing is probably pretty close to optimal using native Matlab code. Depending on what you are doing you may be able to vectorise the inner loop to get a little more efficiency.

For example, it's faster than nchoosek:

N = nchoosek(50, 4);
V = zeros(N, 4);
idx = 0;
tic
for d = 1 : 47
    for c = d+1 : 48
        for b = c+1 : 49
            for a = b+1 : 50
                idx = idx + 1;
                V(idx, :) = [d c b a];
            end
        end
    end
end
toc

tic
V = nchoosek(1:50, 4);
toc

On my machine I get 0.1 and 0.6 seconds, respectively. The approach is still feasible with 50 and 7 too - on my machine it only takes about 1.1 seconds to iterate through all ~100,000,000 combinations (obviously you shouldn't fill up a matrix (like V) that big though, you'll slay your memory).

Sometimes simple is best.

[endeavour90]

I notice that the nested loop method is not that flexible. If I want to generate subset of 4 to 15, then I need to change the code by adding 1 'for' loop for each case. However if I used nchoosek or vchoosek function, then I just need to use 1 loop, say

for i = 4 : 15

nchoosek(1:50,i)

end

However, the only downside is that I want to generate the set row by row instead of the whole matrix at once.

Answer 4

[Richard Brown]

If you want to use native Matlab looping, but keep the benefit of flexibility (different n or k), then you can unroll the loops:

N = nchoosek(n, k);
v = 1:k; % first v
L = (n-k+1):n;
for i = 2:N
  v(k) = v(k) + 1;
  j = k;
  while v(j) == (L(j) + 1)
    v(j:k) = (v(j-1) + 2):(v(j-1)+2+k-j);
    v(j-1) = v(j-1) + 1;
    j = j - 1;
  end
  % useful v for your iteration is here
end

This code can probably be optimised a bit, but it will do what you want - the v vector at the end of each iteration is what you'd use. It will be a bit slow on 50C7 - 23 seconds on my computer, but that's not hugely surprising.