我们有以下公式来确定我们可以从一组 n 中选择多少种大小为 k 的组合 C：
我编写了一个算法，它总是会给出答案 if，当然，答案落在范围内数据类型的（ulong，在我的情况），通过在评估过程中因式分解和取消分子和分母上的项。
尽管尝试计算 C 并在结果太大时检测溢出非常快，但如果我可以放入 n 和 k< 会更好/code> 到一个初步函数中，该函数估计答案是否大于 ulong 可以容纳的大小。它不必是精确的。如果它估计给定的 n 和 k 不会溢出，但它确实溢出了，那很好 - 但它永远不应该说它将会溢出，如果不会的。理想情况下，这个函数应该非常快，否则没有意义——我不妨尝试直接计算 C 并让它溢出。
我正在绘制各种 n 的 nCk 曲线作为 k 的函数，看看我是否能找到一条增长至少与 C(n, k) 一样快但在我的范围内不会偏离太远的曲线对 (0..2^64-1) 感兴趣并且在计算上易于评估。
我没有任何运气。有什么想法吗？
We have the following formula for determining how many combinations C we can pick of size k out of a set of n:
I have written an algorithm which will always give an answer if, of course, the answer falls within the range of the datatype (ulong, in my case), by factorising and cancelling terms on the numerator and denominator during evaluation.
Even though it's quite fast to try to compute C and detect an overflow if the result is too large, it would be better if I could put n and k into a preliminary function which estimates whether the answer will be larger than what ulong can hold. It doesn't have to be exact. If it estimates that a given n and k will not overflow but it does, that's fine - but it should never say this it will overflow if it won't. Ideally this function should be very fast otherwise there is no point in having it - I may as well try and compute C directly and let it overflow.
I was plotting the curve of the nCk for various n's as a function of k to see if I can find a curve which grows at least as fast as C(n, k) but doesn't diverge too far in the range I'm interested in (0..2^64-1) and is computationally easy to evaluate.
I didn't have any luck. Any ideas?
发布评论
评论（1）
如果没有看到你的算法的实际代码，我无法给你 100% 的解决方案，但你最好的选择是开发一个启发式函数。通过简单地找到回归。
r的最小值，对于各种 n 值，nCr 的最终答案会溢出，那么您应该能够分析 n 之类的东西与 n 和 r 之间的比率 (n/r) 之间的关系，并找到一个快速计算函数，让您知道是否溢出将通过我发现对于任何
n < 68，你不应该溢出最终答案，因为 67C33 = 67C34 ~ 1.42x1019 是最大可能的答案，ulong可容纳 ~1.84x1019。类似地，当 n > 时5000，任何r>； 5或nr < n-5肯定会溢出。您可以根据自己的喜好调整这些截止值，对于它们之间的所有 n 值，只需计算 n/r 并使用回归公式来决定是否会溢出或不是。这可能工作量太大，但至少应该让您走上正确的道路。
Without seeing the actual code for your algorithm, I can't give you a 100% solution, but your best bet is to develop a heuristic function. By simply finding the smallest value of
rfor which the final answer to nCr overflows for a variety of n values, you should then be able to analyze the relationship between something like n and the ratio between n and r (n/r), and find a quick to calculate function which would let you know if overflow would occur via regression.I found that for any
n < 68, you should never overflow on the final answer, as 67C33 = 67C34 ~ 1.42x1019 is the largest possible answer, and aulongholds ~1.84x1019. Similarly, whenn > 5000, anyr > 5orn-r < n-5will certainly overflow. You can tune these cutoffs to your liking, and for all the n values in between them, just calculate n/r and use the regression formula to decide if it will overflow or not.This might be too much work, but it should at least get you started on the right path.