how can we estimate memory requirements for nchoosek?

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

[Stephen23]

Original question:

https://www.mathworks.com/matlabcentral/answers/412578-is-there-an-alternative-to-nchoosek-which-is-too-slow

"how can we estimate memory requirements for nchoosek?"

Number of combinations * number of elements per combination * bytes per element

Answer 1

[dpb]

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

[dpb]

Moved to Comment -- dpb

Understood. Nonetheless ... question still stands ... how can we graduate beyond pre-primary school level (where kits learn to count to 20 :)) ) and enhance a bit the 15 limit above ...

Is there any for or in-memory compression possible/feasible - taking the simplest and most convenient case (perhaps unsigned int), where there is a lot of duplication of simple sequences that could be "tokenised" with shorter IDs ... did anyone thought of that, considering the limit of "about 15" above might be a bit too tight, or say claustrophobic for the average Joe owning a 16GB RAM w/ 1TB SSD (well, in this case Joe is above average, still ... highly undersized for the raw and brutal inner-work of the [otherwise brilliant] nchoosek function)?

Just thinking out loud this could be a great piece of engineering and differentiator from the "bigger ugly serpent cousin" lurking in the dark night :)

Thanks!

[dpb]

I'm sure there are other algorithms in the literature but I've not researched the particular subject. One might look at Knuth; I don't recall whether he touches on combinatorics or not...

[Andy]

I like this answer: https://se.mathworks.com/matlabcentral/answers/93323-is-there-a-command-to-compress-a-matrix-in-memory-in-matlab

Nonetheless in our case there ARE many equal sequences of values so compression could make sense. But I don't see anything baked in that could do this, is it?

[dpb]

>> nchoosek(int16(1:5),3)
ans =
10×3 int16 matrix
...
>> whos ans
Name       Size            Bytes  Class    Attributes
ans       10x3                60  int16              

>> nchoosek((1:5),3)
ans =
...
>> whos ans
Name       Size            Bytes  Class     Attributes

ans       10x3               240  double  
>>

Is 4:1; uint8 would be 8:1 and handle values up to 255; as implemented it may require double() first I don't know and there's still the issue of the specific recursive algorithm used that probably could be improved on.

For the latter, as recommended earlier, see The Art of Computer Programming Vol 4 Generating All-tuples and Permutations