MATLAB: How can we estimate memory requirements for nchoosek

#nchoosekMATLAB

nchoosek is a memory intensive command … to the point it can easily kneel down your system … or get something back as the below:

Error using nchoosek>combs (line 175) Out of memory. Type HELP MEMORY for your options.

Error in nchoosek>combs (line 174) Q = combs(v(k+1:n),m-1);

Error in nchoosek (line 132) c = combs(v,k);

Error in NChooseKR (line 7) parfor i = kRange

Best Answer

>> help nchoosek
nchoosek Binomial coefficient or all combinations.
 ...
  nchoosek(V,K) where V is a vector of length N, produces a matrix
  with N!/K!(N-K)! rows and K columns.  Each row of the result has K of
  the elements in the vector V.  This syntax is only practical for
  situations where N is less than about 15.
 ...

TMW writes documentation for a reason...

Related Solutions

MATLAB: Is there an alternative to nchoosek which is too slow

Well, you're asking for 40!/(10! 30!) elements -->

>> N=prod(31:40)/factorial(10)
N =
 847660528
>>

elements so it's not terribly surprising it might just take a while for the scribes to write 'em all down...

It boils down in the end to

function P = combs(v,m)
    n=length(v);
    P = [];
    if m < n && m > 1
        for k = 1:n-m+1
            Q = combs(v(k+1:n),m-1);
            P = [P; [v(ones(size(Q,1),1),k) Q]]; %#ok
        end
    end
end

which has a big problem in time in that P isn't preallocated.

ADDENDUM

Unfortunately, combnk has the same flaw using almost identically the same code.

Whether somebody has supplied mex file or other solution on FEX I didn't research.

MATLAB: Generate large nchoosek in batches

No. Nchoosek is not written in any way to allow you to choose only some reduced subset. In fact, the set of 200 bit binary numbers has a HUGE number of subsets with 5 bits set. I debated showing you how to write such a code, but then you would immediately want to compute combinations of 6 or 7 or 50 of the elements from that set in batches, and you would very quickly overwhelm even a batched version.

The set of combinations that you want to generate gets HUGE, and does so very quickly.

I'll relent just a tiny bit though. The set that you want to generate is simple enough to compute.

Consider if bit 1 is set. Then you need to generate all sets of 199 bits, with exactly 4 of them chosen. You already know how to do this. If bit 1is not set, then you need to generate all possible subsets of 5 bits, choosing from 199 bits. So you can do the whole thing recursively, until the sets become small enough to generate.

Best Answer

Related Solutions

MATLAB: Is there an alternative to nchoosek which is too slow

MATLAB: Generate large nchoosek in batches

Related Question