COMBN (4.2)

All combinations of N elements taken from the vector V.

Description

COMBN - all combinations of elements
  M = COMBN(V,N) returns all combinations of N elements of the elements in
  vector V. M has the size (length(V).^N)-by-N.
 
  [M,I] = COMBN(V,N) also returns the index matrix I so that M = V(I).
 
  V can be an array of numbers, cells or strings.
 
  Example:
    M = COMBN([0 1],3) returns the 8-by-3 matrix:
      0 0 0
      0 0 1
      0 1 0
      0 1 1
      ...
      1 1 1
 
  All elements in V are regarded as unique, so M = COMBN([2 2],3) returns
  a 8-by-3 matrix with all elements equal to 2.
 
  NB Matrix sizes increases exponentially at rate (n^N)*N.
  

  See also PERMS, NCHOOSEK
  and ALLCOMB, PERMPOS here on the FEX

Latest version 4.2 (apr 2011)

• Acknowledgements: This submission has inspired the following:; N_PERMUTE_K, VChooseKRO, de Bruijn sequence generator, Kautz sequence generator
• MATLAB release: MATLAB 7 (R14)

[Jamie Baier]

Does what it says, but there really should be an option to treat elements as non-unique.

[Jos vdG]

Jamie, use COMBN(UNIQUE(V),N)

[yakir gagnon]

 

[Richard Vance]

Easy to use, fast, and suitable for incorporating into other programs. Good documentation well organized. It really helped me solve some problems.

[David Torres]

Great tool. Easy to use.

[Jürgen Womser-Schütz]

Very fast! Very helpful to solve my actual problem.

[Peter Navé]

What I needed!

[B E]

Thanks! Exactly what I needed.

[Vangelis R]

I am very surprised this is not a build in function. You saved my day thanks a lot!

[ShenKae Wu]

Thanks a lot

[Wolfgang Zieroth]

Fast and (almost) exactly what I needed!

... I only need those combinations which sum to (say) one. I can, of course, first create all combinations with this program and then find(m*ones(N,1)==1). Yet I bounce very quickly against maximum variable size for Matlab. Any Suggestions?

[Kaijun Wang]

It is very useful, thanks !

[Jos the author]

Roger Stafford pointed out that, due to the IEEE 754 standard, the floor of a floating point (as used in COMBN's algorithm) may lead to faulty results for very specific inputs.
The update incorporates his excellent solution to this potential problem. Thanks Roger!
The update (COMBN version 3.2) should be up soon ...

[Ohad N]

Does the job...

[Antonio Silva]

Thanks a million!

[Riccardo Bevilacqua]

Exactly what I was looking for!

[jose caceres]

any idea of how to get the combinations without repetition of previous combinations, and without re-using the elements in a a selection?
 

[Carlos Baiz]

Thanks!

[Philip L]

 

[Jan Simon]

Nice and comapct program! H1-line, help, history, comments in the code, efficient. Thanks!

But can be made still a little bit faster:
    X = repmat({X},1,N) ;
    [X{1:N}] = ndgrid(X{:}) ;
    X = fliplr(reshape(cat(N+1,X{:}),[],N)) ;
1. If X is filled in reverse order with [X{N:-1:1}], FLIPLR can be omitted => 25% faster for COMBN(1:10, 5) (see my comment for ALLCOMB)
2. Inside NDGRID the same operations are performed for each input, but all inputs are equal. Inlining and simplyfying NDGRID leads to (REPMAT can be omitted then):
    C = cell(1, N);
    X = X(:);
    L = length(X);
    s(1:N - 1) = L;
    X = reshape(X(:, ones(1, prod(s))), [L, s]);
    C{N} = X;
    for iC = 2:N
       C{N - iC + 1} = permute(X, [2:iC, 1, iC + 1:N]);
    end
    X = reshape(cat(N+1, C{:}), [], N);
=> 40-50% faster.
To my surprise it is *slower* to create the output array at once and insert the permuted subarrays directly.

[Oleg Komarov]

Can't find a better suited H1-line. Neat help, simple example, history (maybe more details on the dates...) and past algorithms too.
I don't use combinatorics very much but I always wonder why matlab doesn't cover it esplicitly. A must have.

Oleg

[John D'Errico]

 

[Fabio]

Does anyone have an idea on how to create a function like "combn" but where the generated matrix contains only monotone rows? I could do it manually by removing non-monotone rows after having built the matrix, but when the size of the matrix becomes large i got out of memory error. Any idea?

[Brad Ridder]

Excellent, just what I needed. Thanks!

[Manu]

Excellent and fast!

[W. Owen Brimijoin]

The core of this function is a lovely little computational gem. Thank you.

[Talaria]

works great, but is there a way to beat the limitation? for example i want to be able to return the following:
M = COMBN([0 1],150)
is this possible?

[Jos (10584)]

@ Talaria, this is impossible as it would require a memory of (at least) 150*(2^150) bits which is about 2700000000000000000000000000000000 Terabyte ...

However, it is unlikely that you need all those combinations at once; perhaps you can think of another approach to your problem, for instance, by drawing a few random combinations at a time?

[Marc Lalancette]

Nice code, thanks! Just for fun, slight to medium speed improvement (sorry my k = your N):

%instead of:
%[Y{k:-1:1}] = ndgrid(X) ;
%Y = reshape(cat(k+1,Y{:}),[],k) ;
%fill Y directly:
    nX = numel(X);
    Y(nX^k, k) = X(1); % Initialize to give shape and data type.
    s(1:k-1) = {ones(1, nX)};
    for i = 1:k
      Y( ((i-1)*nX^k + 1) : (i*nX^k) ) = X(s{1:i-1}, :, s{i:k-1});
      X = permute(X, [1:i-1, i+1, i]);
    end
% This has inverse order for the combinations as you had, easy to change.

[Jos (10584)]

@Marc, thanks for your interest and suggestions for improvement. Yet, for code compatibility (and fairness) you need to implement to inverse order step as well :-)

[Han]

Repetitive combination, great!

[mya]

verry useful, thank you