is there an alternative to nchoosek which is too slow?

Question

Andy 2018-7-29

0
链接

此问题的直接链接

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

编辑： John D'Errico 2024-1-2

采纳的回答： dpb

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

Thanks

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

dpb 2018-7-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/412578-is-there-an-alternative-to-nchoosek-which-is-too-slow#answer_330796

编辑：dpb 2018-7-29

在 MATLAB Online 中打开

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.

7 个评论
显示 5更早的评论隐藏 5更早的评论

Walter Roberson 2024-1-2

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

John D'Errico 2024-1-2

编辑：John D'Errico 2024-1-2

在 MATLAB Online 中打开

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.

请先登录，再进行评论。