0

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}.

endeavour90
  • 87
  • 3
  • 7
  • 1
    Matlab has parallel loops. search for 'parfor' in the docs – Griffin Apr 01 '12 at 01:25
  • I have tried to add replace for N = 4 : 50 with parfor N = 4 : 50 , but it turned out to be slower. – endeavour90 Apr 01 '12 at 02:07
  • 2
    `parfor` only parallelizes if you have a `matlabpool` set up, which requires the parallel computing toolbox. The actual `parfor` command is a part of base Matlab so that developers can work without that toolbox, and then fold it into a session with additional toolboxes later on. – Pursuit Apr 01 '12 at 02:30

2 Answers2

1

Fun problem!

Enumerating all possible combinations is well-studied and there are many solutions. See for example this SO question. Here is a simple, efficient solution for reasonable choices of N, k using two convenient Matlab functions, nchoosek and arrayfun:

% test function for benchmarking
foo = @(a, b, c, d) ( a + b + c + d );

% see detailed timings at https://gist.github.com/2295957
tic;
C = nchoosek([1:50], 4);     % all 230,300 4-tuple combinations
result = arrayfun(@(k) foo(C(k,1),C(k,2),C(k,3),C(k,4)), 1:length(C));
toc;
Community
  • 1
  • 1
Andrew B.
  • 1,010
  • 6
  • 19
  • +1, elegant answer. I question your timing though. I can run your code in 6.4 sec, and the original code (modified to collect results into a 230300X1 matrix) in 5.0 seconds. (R2011a) – Pursuit Apr 02 '12 at 23:14
  • @Pursuit Motivated by your commment, I wrote a test strap (https://gist.github.com/2295957) for more precise benchmarking. It's simple, but confirms that my initial times were off. The new timings suggest that (properly counting) nested loops are the fastest solution by an order of magnitude (0.1232 secs vs 2.62 secs median run time on my R2011a setup). This is surprising to me. – Andrew B. Apr 03 '12 at 22:35
  • I love some real test data. Thanks! I'm surprised that you were able to to an order of magnitude, but I'm not surprised that the loops are faster. Matlab is very efficient with simple loops, and the simple loops are a minimum-memory implementation. Whereas the arrayfun call is not particularly fast, and a lot of memory has to be allocated to keep track of the values in `C`. When I get into micro-optimization, I often end up with more simple loops and fewer high level, beautiful calls. However, I think your answer address the initial question. Hopefully @endeavour90 will accept it. – Pursuit Apr 03 '12 at 23:31
0

It looks like the purpose of the code could be stated as calling SomeFunction with all possible inputs which meet the following conditions:

  1. A < B < C < D
  2. D <= 50
  3. (Implied, A, B, C, D are integers)

If that is the case, you can make this code a lot faster by eliminating the outermost loop. That is, replace for N = 1:50 with N = 50. As it is, you are calling the same combinations many times. For example, replacing the first line with N = 4:6 returns the following result ("*"ed lines are duplicated):

 A     B     C     D
 N=4
 1     2     3     4

 N=5
 1     2     3     4 *
 1     2     3     5
 1     2     4     5
 1     3     4     5
 2     3     4     5

 N=6
 1     2     3     4 *
 1     2     3     5 *
 1     2     3     6
 1     2     4     5 *
 1     2     4     6 
 1     2     5     6
 1     3     4     5 *
 1     3     4     6 
 1     3     5     6
 1     4     5     6
 2     3     4     5 *
 2     3     4     6
 2     3     5     6
 2     4     5     6
 3     4     5     6
Pursuit
  • 12,285
  • 1
  • 25
  • 41
  • That's what I thought. Remove the outer loop and replace with N=50. – Pursuit Apr 01 '12 at 03:24
  • Ok, Let say N = 50 I am looking for alternative of getting combination of increasing 4-tuple from 1,2,3,...50 without using 4 for loop i.e. (1 2 3 4), (1 2 3 5),..., (1 2 3 50), (1 2 4 5), ...(47 48 49 50) – endeavour90 Apr 01 '12 at 03:32
  • 1
    I suspect that there is a cleaner and more beautiful way. I'll update this answer when/if I figure one out (or someone else may post one). I don't think that there will be a faster way. – Pursuit Apr 01 '12 at 03:38
  • Hi, I changed the problem. Hopefully, it is easier to understand. Thanks – endeavour90 Apr 01 '12 at 04:23