2011年5月7日土曜日

組合せ数 (nCr) の計算

組合せ数(nCr)の計算例です(漸化式、Pascalの3角形による方法)。

n 個の数から r 個を選択する場合の組合せ数を計算します。
通常、組合わせ数 nCr は以下のような漸化式により計算することができます。

また、重複がある場合の組合せ数は以下のように計算することができます。

例では、選択する数に重複がある場合とない場合(選択する数が同じでも順番のみが異なっている場合)に分けて計算しています。

重複がある場合には値が非常に大きくなってしまうため、どの辺までオーバーフローなく計算できているか、若干疑問です。
漸化式による計算と、Pascal の方法による計算を比較していますが、Pascal の方法による計算の方が、加算により計算しているのでオーバーフローは少ないかと思われます。

全ての順列、組み合わせを配列として取得する例は、こちら

実行結果

0 件のコメント:

コメントを投稿