Code covered by the BSD License  

Highlights from
NCHOOSE (v2.1 mar 2010)

5.0

5.0 | 4 ratings Rate this file 12 Downloads (last 30 days) File Size: 2.71 KB File ID: #20011

NCHOOSE (v2.1 mar 2010)

by

 

22 May 2008 (Updated )

return all combinations of the elements of a set

| Watch this File

File Information
Description

NCHOOSE - all combinations of the elements of a set
W = nchoose(S) returns all possible combinations of one or more
elements of the set S. In total there are 2^N-1 combinations, where N
is the number of elements in S. W is a cell array: each cell holds one
of these combination (as a row vector). S can be a cell array of
strings, and each cell of W will then contain a cell array of strings.

Example:
   nchoose([2 4 6 8])
     % -> { [2] ;
     % [4] ;
     % [2 4] ;
     % [6] ;
     % ...
     % [2 6 8] ;
     % [4 6 8] ;
     % [2 4 6 8]} ; % in total (2^4)-1 = 15 different combinations
 
Notes:
- For sets containing more than 18 elements a warning is given, as this
can take some time. On my PC, a set of 20 elements took 20 seconds. Hit Ctrl-C to intterupt calculations.
- If S contain non-unique elements (e.g. S = [1 1 2]), NCHOOSE will return non-unique cells. In other words, NCHOOSE treats all elements of S as being unique. One could use NCHOOSE(UNIQUE(S)) to avoid that.
- Loosely speaking, NCHOOSE(S) collects all output of multiple calls to NCHOOSEK(S,K) where K is looping from 1 to the number of elements of S. The implementation of NCHOOSE, however, does rely of a different method and is much faster than such a loop.
- By adding an empty cell to the output, the power set of a cell array
      is formed:
        S = {1 ; 'hello' ; { 1 2 3}}
        PowerS = nchoose(S)
        PowerS(end+1) = {[]}
      See: http://en.wikipedia.org/wiki/Power_set
   
See also NCHOOSEK, PERMS
and COMBN, ALLCOMB on the File Exchange

(version 2.1, mar 2010)

Acknowledgements

This file inspired Nchoosecrit (V1.0 Feb 2013).

MATLAB release MATLAB 6.5 (R13)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (7)
22 Mar 2012 Marc Lalancette

Theoretical note, in case someone (as I did) wants to get a limited number of random combinations, then this method fails for N > 51 since then eps(2^52) = 1, i.e. can't represent the integers accurately any more with double type. Of course, here we run out of memory with such a large N anyway.

Also, with bitget, I was using a loop over bits instead of a loop over combinations. I haven't checked, but I assumed it would be faster. I'm also going to check with d2b instead of bitget. (found on FEX, and modified to work on arrays).

27 Dec 2010 Eric  
19 Mar 2010 Joshua Carmichael

Vectorized, and just what I need. Very fast.

28 May 2008 Urs (us) Schwarz

as had to be expected from this author: exemplary ML-typical implementation of an evergreen-request on CSSM with good help and copious comments for its sleek computational engine.
this is a true add-on to the family of (basic) ML functions like dec2bin - and one wonders why it has not been supplied by TMW from the very beginning (or at leas since the implementation of CELLs) because users from many different fields will be able to use it.
us

24 May 2008 Jos (the author)

Very useful thoughts indeed. Thanks us! The update (v2.0) incorporates the (slightly altered) bitget implementation.

23 May 2008 Urs (us) Schwarz

as usual, interesting stuff, jos.
a few remarks:
- it should be mentioned that UNIQUE refers to the position uniqueness as something like
>> nchoose([1,1,1]);
will yield (seemingly) equal combinations
- there should be an error check for M > 23
- a speed improvement
W=cell(M,1);
p2=pow2(1-numel(S):0);
for i=1:M,
Q=rem(floor(i * p2),2)==1 ;
W{i}=S(Q); % take consuming FLIPLR out!
end
W=cellfun(@(x) x(end:-1:1),W,'uni',false);

i used this approach in the past, which yields a speed gain of approximately 2.6

% note: all checks/comments take out...
function cmb=pcomb(pat)
nb=numel(pat);
mc=(2.^nb)-1;
pp=2.^(nb-1:-1:0).';
cmb=cell(mc,1);
for i=1:mc
cmb{i,1}=pat(bitget(i*pp,nb)~=0);
end
end

comparison on a wintel:
ic2.2*2.4mhz/2gb/winxp.sp2/r2007b

len: ...pcomb | .nchoose | ....gain
01: 0.000040 | 0.000107 | 3.202227
02: 0.000043 | 0.000119 | 3.228383
03: 0.000046 | 0.000148 | 3.302875
04: 0.000075 | 0.000238 | 3.082459
05: 0.000127 | 0.000387 | 3.065482
06: 0.000232 | 0.000714 | 3.120286
07: 0.000447 | 0.001342 | 2.991717
08: 0.000908 | 0.002625 | 2.878488
09: 0.001813 | 0.005216 | 2.881585
10: 0.003804 | 0.010127 | 2.655678
11: 0.007689 | 0.020627 | 2.682076
12: 0.015583 | 0.041467 | 2.657087
13: 0.031492 | 0.082831 | 2.624573
14: 0.064452 | 0.168786 | 2.617609
15: 0.130970 | 0.341670 | 2.607633
16: 0.268776 | 0.688592 | 2.560370
17: 0.585902 | 1.393225 | 2.379455
18: 1.285114 | 2.812605 | 2.188545
19: 2.782169 | 5.672041 | 2.039558
20: 6.063693 | 11.488511 | 1.894641
21: 13.237517 | 22.986104 | 1.736436
22: 28.864961 | 46.540510 | 1.612353

just a few thoughts
us

22 May 2008 John D'Errico

Ok, I'll admit that I'd have expected this would already have been on the FEX or in Matlab. And for myself, I'd just use the simple dec2bin(1:(2^n))=='1'. After all, a set is defined in Matlab only by your representation of it. Numbers are merely symbols, and symbols have meaning only in context.

On the other hand, this is nicely written. It takes the dec2bin solution one step further, so it could clearly be of use to others. It has good help, with an example.

The author has taken great pains in the code to document why he chose the method used. Its a style I'd highly recommend for others. In some future time when you need to revisit your code, you will very much appreciate these notes. Or if someone else wants to read your code, they will wonder why you chose to solve the problem as you did. These comments answer all of those questions. Well done.

Updates
27 May 2008

(v1.1) fixed spelling errors

15 Mar 2010

reference to powerset

Contact us