perl - Perl 中 nCk 的高效内联实现

Question

是否有任何现有的实现可以在 Perl 中计算这个？

 nCk (n choose k), or n!/(k!*(n-k!))

那只返回一个数字，而不是组合列表。

Answer 1

Math::Counting定义了必要的函数。您可以复制并粘贴以下内容并在没有任何外部模块的情况下使用它：

sub combination {
    my( $n, $r ) = @_;
    return unless defined $n && $n =~ /^\d+$/ && defined $r && $r =~ /^\d+$/;
    my $product = 1;
    while( $r > 0 ) {
        $product *= $n--;
        $product /= $r--;
    }
    return $product;
}

但是，对于任意精度，您应该使用Math::BigInt。同样，您可以使用Math::Counting中的函数：

sub bcomb {
    my( $n, $k ) = @_;
    $n = Math::BigInt->new( $n );
    $k = Math::BigInt->new( $k );
    my $r = $n - $k;
    return $n->bfac() / ($k->bfac() * $r->bfac());
}