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());
}