Matlab, alternative to nested for loop

Question

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

I have tried to add replace for N = 4 : 50 with parfor N = 4 : 50 , but it turned out to be slower. — endeavour90
– endeavour90, Commented Apr 1, 2012 at 2:07
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
– Pursuit, Commented Apr 1, 2012 at 2:30

Community · Accepted Answer · 2017-05-23 12:20:15Z

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;

edited May 23, 2017 at 12:20

CommunityBot

11 silver badge

answered Apr 1, 2012 at 8:16

Andrew B.

1,0586 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Pursuit Over a year ago

+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)

Andrew B. Over a year ago

@Pursuit Motivated by your commment, I wrote a test strap (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.

Pursuit Over a year ago

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 · Accepted Answer · 2012-04-01 03:20:33Z

0

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

A < B < C < D
D <= 50
(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

edited Apr 1, 2012 at 3:20

answered Apr 1, 2012 at 3:10

Pursuit

12.4k1 gold badge28 silver badges42 bronze badges

4 Comments

Pursuit Over a year ago

That's what I thought. Remove the outer loop and replace with N=50.

endeavour90 Over a year ago

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)

Pursuit Over a year ago

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.

endeavour90 Over a year ago

Hi, I changed the problem. Hopefully, it is easier to understand. Thanks

Collectives™ on Stack Overflow

Matlab, alternative to nested for loop

2 Answers 2

3 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related