MATLAB Answers

is there an alternative to nchoosek which is too slow?

13 views (last 30 days)
Andy
Andy on 29 Jul 2018
Answered: Andy on 3 Aug 2018
Try cnk = nchoosek(1:40, 10) and you'll see how slow it is. Is there an alternative?
Thanks

Accepted Answer

dpb
dpb on 29 Jul 2018
Edited: dpb on 29 Jul 2018
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.
  2 Comments
dpb
dpb on 29 Jul 2018
Yes, I meant the combinations, not elements.

Sign in to comment.

More Answers (1)

Andy
Andy on 3 Aug 2018
not if some sort of (in-memory?) compression is applied ... if that's even possible. but looking at the brutal return of say nchoosek(25,15) - there might be a good potential for tokenization of repeating patterns - if that makes sense.
thanks

Community Treasure Hunt

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

Start Hunting!