問題タブ [binomial-coefficients]

長さ n の配列が与えられた場合、配列の辞書式インデックス (ゼロからのインデックス) を出力する必要があります。辞書式インデックスは基本的に、元の配列のすべての可能な順列を含むスーパー配列に配置された場合に、指定された配列が持つ位置です。

これはそれほど難しいことではありません（Unique Element Permutations）が、私の問題は同じアルゴリズムを作成することですが、同じ要素の重複を含む配列に対してです。

以下は、小さな配列の可能な順列のいくつかと、それぞれの予想される戻り値を示すグラフの例です。

最も重要なことは、問題を解決するために他の順列を生成せずにこれを実行したいということです (たとえば、指定された順列よりも少ないすべての順列を生成したくありません)。

疑似コードを探しています。概念を理解できる限り、特定の言語は必要ありません。疑似コードを使わない計算原理でもいいです。

私は似たようなことを行ういくつかの実装を見てきましたが、バイナリ文字列 (2 つの異なるタイプの要素のみを含む) を対象としており、それらは二項係数を使用して仕事を完了させていました。うまくいけば、それは役に立ちます。

ncrこの投稿に出くわしたとき、私は可能な効率的な計算方法を読んでいました 。

nCr を計算するより良い方法はどれですか

ここで与えられた2番目の答えは、私には理解できません。コードは次のとおりです。

そして、これの複雑さは何ですか？例でやってみたら正解が出たのですが、その条件は何ですか？

モジュラ演算がプログラミングでどのように機能するかを誰かに説明してもらえますか? 大きな値を操作するために使用されることは知っています。

たとえば、int データ型を使用して B(1000000, 2) の二項係数を計算するには、次のようにします。1000000 のような大きな値の階乗を計算する必要があるため、int データ型を使用して乗算することはできなかったと思います。これには数百万の桁があり、32 ビットまたは 64 ビットの整数には収まりません。

剰余算術がこれらのタイプの問題に使用されていることは知っていますが、それがどのように機能するか正確にはわかりません。

私は haskell で櫛関数を書いています。必要なことは、カードのデッキを提供するときに、サイズ x のそのデッキから可能な手のすべての組み合わせを提供することです。

これは関連するコードです

しかし、コーム 5 [1..52] を計算するように依頼すると、たとえば、完全なデッキから 5 の手札が得られず、結果が得られず、非常に長い間実行され続け
ます。このアルゴリズムを高速化する方法は?

n testCount 値の nCr を計算するコードを以下に記述しました。 それは私の価値観ではうまくいくようですが、ハッカーアースのテストケースは失敗します。

` 簡略化された分子と分母のケース

} `

これは t 個のテスト ケースを持つ非常に単純なプログラムであり、nCr=n!/r!*(nr)! を見つける必要があります。したがって、20C2 のような小さな値ではうまく機能しますが、100C10 のような大きな値では機能しません。32C2=-6 ,100C10 浮動小数点例外が発生します。1<=n<=r<=1000 にする方法 ?? 注: long double を要求していないか、float に変更したくありません。答えは 100C10 = 17310309456440 同様に 989C45=? のようになります。