W = nchoose(S) returns all possible combinations of 0, 1, or more

elements of the set S, having N elements. There are 2^N combinations

in total. W is a cell array and each cell holds one of these

combination (as a row vector).

S can be a cell array, and each cell of W will then contain a cell

array. W is the powerset of S, as it includes the empty set (0

elements) as it first cell.

For a vector of integers I, W = nchoose(S, I) returns only the sets

indicated by the indices I. This might be useful for large sets.

Examples:

nchoose([2 4 6 8])

% -> { [] ;

% [2] ;

% [4] ;

% [2 4] ;

% [6] ;

% ...

% [2 6 8] ;

% [4 6 8] ;

% [2 4 6 8]} ; % in total 16 different combinations

nchoose([33 22 11], [1 8 4])

% -> { [] ; [33 22 11] ; [ 33 11]}

Notes:

- For sets containing more than 18 elements a warning is given, as this

can take some time. 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.

- For more information, see: http://en.wikipedia.org/wiki/Power_set

See also nchoosek, perms,

permn, nchoose2, allcomb on the file Exchange

Jos (10584) (2020). nchoose (https://www.mathworks.com/matlabcentral/fileexchange/20011-nchoose), MATLAB Central File Exchange. Retrieved .

Created with
R2018a

Compatible with any release

**Inspired:**
nchoosecrit(S, FUN)

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Marc LalancetteTheoretical 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).

EricJoshua CarmichaelVectorized, and just what I need. Very fast.

Urs (us) Schwarzas 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

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

Urs (us) Schwarzas 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

John D'ErricoOk, 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.