标签: binomial-coefficients

我所说的"大n"是数以百万计的东西.p是素数.

我已经尝试了 http://apps.topcoder.com/wiki/display/tc/SRM+467 但是这个功能似乎是不正确的(我用144选择6 mod 5测试了它,当它应该给我时它给了我0 2)

我试过 http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 但我完全不明白

我还做了一个memoized递归函数,它使用逻辑(组合(n-1,k-1,p)%p +组合(n-1,k,p)%p)但是它给了我堆栈溢出问题因为n很大

我尝试过卢卡斯定理,但它似乎要么缓慢还是不准确.

我所要做的就是为大n创建一个快速/准确的n选择k mod p.如果有人能帮我展示一个很好的实现,我将非常感激.谢谢.

根据要求,对于大n的命中堆栈溢出的memoized版本:

std::map<std::pair<long long, long long>, long long> memo;

long long combinations(long long n, long long k, long long p){
   if (n  < k) return 0;
   if (0 == n) return 0;
   if (0 == k) return 1;
   if (n == k) return 1;
   if (1 == k) return n;

   map<std::pair<long long, long long>, long long>::iterator it;

   if((it = memo.find(std::make_pair(n, k))) != memo.end()) {
        return …

我有兴趣找到第n行pascal三角形(不是特定元素,而是整行本身).最有效的方法是什么？

我想到了通过总结上面行中相应元素来构造三角形的传统方法:

1 + 2 + .. + n = O(n^2)

另一种方法可能是使用特定元素的组合公式:

c(n, k) = n! / (k!(n-k)!)

对于行中的每个元素,我认为根据计算组合的方式,前一种方法需要更多时间.有任何想法吗？

方法1:
C(n,r)= n!/(nr)!r!

方法2:
在wilf的" 组合算法 "一书中,我发现:
C(n,r)可以写成C(n-1,r) + C(n-1,r-1).

例如

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

如您所见,最终解决方案不需要任何乘法.在每种形式C(n,r)中,n == r或r == 1.

这是我实现的示例代码:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

请参见此处的输出

在方法2中,存在重叠的子问题,我们正在调用递归来再次解决相同的子问题.我们可以通过使用动态编程来避免它.

我想知道哪个是计算C(n,r)的更好方法？

如何计算大n和和的二项式系数模数142857 r.142857有什么特别之处吗？如果问题是模数p在哪里p是素数那么我们可以使用卢卡斯定理但是应该为142857做什么.

在这里,我尝试用C++编写程序来查找NCR.但是我在结果中遇到了问题.这是不正确的.你能帮我找一下程序中的错误吗？

#include <iostream>
using namespace std;
int fact(int n){
    if(n==0) return 1;
    if (n>0) return n*fact(n-1);
};

int NCR(int n,int r){
    if(n==r) return 1;
    if (r==0&&n!=0) return 1;
    else return (n*fact(n-1))/fact(n-1)*fact(n-r);
};

int main(){
    int n;  //cout<<"Enter A Digit for n";
    cin>>n;
    int r;
         //cout<<"Enter A Digit for r";
    cin>>r;
    int result=NCR(n,r);
    cout<<result;
    return 0;
}

我需要在Python中进行二项式测试,允许计算10000的数量级别的'n'.

我已经使用scipy.misc.comb实现了一个快速的binomial_test函数,但是,它在n = 1000附近非常有限,我想因为它在计算阶乘或组合本身时达到了最大可表示的数字.这是我的功能:

from scipy.misc import comb
def binomial_test(n, k):
    """Calculate binomial probability
    """
    p = comb(n, k) * 0.5**k * 0.5**(n-k)
    return p

我怎么能使用本机python(或numpy,scipy ...)函数来计算二项式概率？如果可能的话,我需要scipy 0.7.2兼容代码.

非常感谢!

我想在python上计算二项式概率.我试着应用这个公式:

probability = scipy.misc.comb(n,k)*(p**k)*((1-p)**(n-k))

我得到的一些概率是无限的.我检查了一些p = inf的值.对于其中一个,n = 450,000,k = 17.该值必须大于1e302,这是浮点数处理的最大值.

然后我试着用 sum(np.random.binomial(n,p,numberOfTrials)==valueOfInterest)/numberOfTrials

这将绘制numberOfTrials样本并计算绘制valueOfInterest值的平均次数.

这不会带来任何无限的价值.但是,这是一种有效的方法吗？为什么这种方式不会产生任何无限的价值而计算概率呢？

我正在寻找一个高效的Java库(甚至是一个函数)来执行臭名昭着的精确二项式测试.类似于此处描述的R函数"binom.test" .

你能帮助我吗？非常感谢!:-)

我编写了一个给出单词列表的算法,必须检查该单词列表中的四个单词的每个唯一组合(无论顺序如何).

x可以使用二项式系数计算要检查的组合的数量,即x = n!/(r!(n-r)!),n列表中的单词总数在哪里,并且r是每个组合中的单词的数量,在我的情况下总是4,因此函数是x = n!/(4!(n-4)!) = n!/(24(n-4)!).因此,作为总词数n,增加了要检查的组合的数量x,因此在因子上增加了吗？

什么已抛出我是WolframAlpha的能改写这个功能x = (n^4)/24 ? (n^3)/4 + (11.n^2)/24 ? n/4,所以现在它会出现增长多项式的n增长？那是哪个？!

这是一个可视化函数增长的图表(字母x切换为l)

给定具有n个键的数组或对象,我需要找到具有长度的所有组合x.
给定X是可变的.binomial_coefficient(n,x).

目前我正在使用这个:

function combine(items) {
    var result = [];
    var f = function(prefix, items) {
        for (var i = 0; i < items.length; i++) {
            result.push(prefix + items[i]);
            f(prefix + items[i], items.slice(i + 1));
        }
    }
    f('', items);
    return result;
}

var combinations = combine(["a", "b", "c", "d"]);

输出是:

["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"]

因此,如果我想要二项式系数x=3,n=4我选择长度等于三的所有字符串.{abc,abd,acd,bcd}.

所以我分两步完成.

是否有更高效的算法,复杂度更低？

链接: 解决方案性能(JSPerf)