is there an alternative to nchoosek which is too slow?

Try cnk = nchoosek(1:40, 10) and you'll see how slow it is. Is there an alternative?

Thanks

Answer 1

[dpb]

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.

[Matt J]

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

Ten times that, in fact. 40!/(10! 30!) is the number of combinations, but there are 10 elements in each combination. Even in uint8, it will be an 8GB array.

[dpb]

Yes, I meant the combinations, not elements.

[Andy]

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

[Andy]

8GB is not that big nowadays ... plus the pre-allocation issue can be "fixed" somehow I guess?

Also, why would the for loop above NOT be "convertible" to a parfor, for faster processing? (which would be an amazing "dogfooding" example)

thx

[Walter Roberson]

@Andy

The loop is not convertible to parfor() because the code is recursive. Well, it could be done but only the outer loop could be done in parallel.

[Walter Roberson]

The internal code of nchoosek() does not use a recursive function -- and the internal code of nchoosek() does pre-allocate

[John D'Errico]

It does not matter how fast you make nchoosek, if you were able to magically make nchoosek faster, perhaps using parfor, etc., then @Andy would want to generate

cnk = nchoosek(1:40, 11)

or something bigger yet.

Anyway, note that MOST people do not have access to the parallel computing toolbox. So TMW will not be allocating much programmer time to make the code faster for the few people who could make use of an acceleration tool. There are lots of things they want to allocate person-hours to than something that few can benefit from, especially since if they did, it would only give a benefit on a few rare cases.

John's rule of computing is something I have stated many times on Answers and previous forums. That is:

"Problems always expand to just a bit bigger than you can feasibly solve using any current computing hardware or algorithms."

The logic is simple, in that if you can solve it easily, then someone already has, and you need to solve a bigger, harder problem than anyone else, one that is not easy.

My response is always that if you are trying to use nchoosek like this, then you are trying to solve the problem the wrong way. You need to be using mathematics intelligently, not brute force. At the very least, you will need to use tools like optimization. Reformulate your problem so that it is solvable. Don't just bemoan the fact that the software is not fast enough to solve all problems using brute force.