4

固定長のビット配列とそれに含まれる 0 と 1 の数が与えられた場合、i 番目の組み合わせを返すのにできるだけ時間がかからないように、考えられるすべての組み合わせをどのように配置できますか? それらが返される順序は重要ではありません。

次に例を示します。

array length = 6
number of 0s = 4
number of 1s = 2

可能な組み合わせ (6! / 4! / 2!) 000011 000101 000110 001001 001010 001100 010001 010010 010100 011000 100001 100010 100100 101000 110000

問題 1番目の組み合わせ = 000011 5番目の組み合わせ = 001010 9番目の組み合わせ = 010100

100001 100010 100100 101000 110000 001100 010001 010010 010100 011000 000011 000101 000110 001001 001010 のように異なる配置で

1 番目の組み合わせ = 100001 5 番目の組み合わせ = 110000 9 番目の組み合わせ = 010100 を返します。

現在、各ビットが 1 か 0 かをテストする O(n) アルゴリズムを使用しています。問題は、非常に長い配列 (10000 ビットのオーダー) を大量に処理する必要があるため、遅い（そしてキャッシングは問題外）。より高速なアルゴリズムが存在する可能性があると思われるかどうかを知りたい.

ありがとうございました

4

3 に答える 3

1

問題を理解できるかどうかはわかりませんが、他の組み合わせを生成せずにi番目の組み合わせのみが必要な場合は、次のアルゴリズムを使用できます。

1に設定されたNビットのC（M、N）= M！/（N！（MN）！）の組み合わせがあり、位置Mに最大で最高のビットがあります。

i番目が必要です。C（M、N）>=iになるまでMを繰り返しインクリメントします。

while( C(M,N) < i ) M = M + 1

これにより、設定されている最上位ビットがわかります。もちろん、組み合わせを繰り返し計算します

C(M+1,N) = C(M,N)*(M+1)/(M+1-N)

見つかったら、N-1ビットの（iC（M-1、N））番目の組み合わせを見つけるのに問題があるため、Nで再帰を適用できます...これ
は、D = C（M + 1、N）-C（M、N）、およびI = I-1で、ゼロから開始します

SOL=0
I=I-1
while(N>0)
    M=N
    C=1
    D=1
    while(i>=D)
        i=i-D
        M=M+1
        D=N*C/(M-N)
        C=C+D
    SOL=SOL+(1<<(M-1))
    N=N-1
RETURN SOL

あなたがその数のビットを持っているならば、これは大きな整数の算術を必要とするでしょう...

于 2012-08-18T23:54:54.333 に答える
0

順序が問題にならない場合 (一貫性を保つ必要があるだけです)、combination(i)が最初に引数を指定して呼び出されたときに、目的の密度を持つ必要なものを返すようにするのが最も速い方法だと思います。私。次に、その値をメンバー変数に格納します (たとえば、値 i をキーとし、返された組み合わせを値として持つハッシュマップ)。2 回目の組み合わせ (i) が呼び出されたときは、ハッシュマップで i を検索し、以前に返されたものを見つけて、もう一度返します。

もちろん、argument(i) の組み合わせを返すときは、それが他の引数に対して以前に返したものではないことを確認する必要があります。

返すように求められる数が組み合わせの総数よりも大幅に小さい場合、combination(i) への最初の呼び出しの簡単な実装は、すべて 0 で適切な長さの値を作成し、num_ones をランダムに設定することです。ビットを 1 にしてから、i の別の値に対して既に返されたものではないことを確認します。

于 2012-08-18T19:30:16.967 に答える
0

あなたの問題は、二項係数によって制約されているようです。あなたが与える例では、問題は次のように翻訳できます。

一度に2つ選択できる6つのアイテムがあります。二項係数を使用すると、ユニークな組み合わせの総数は N! と計算できます。/ (K! (N - K)!、これは、K = 2 の場合、N(N-1)/2 に単純化されます。N に 6 を代入すると、15 が得られます。これは、計算した組み合わせの数と同じです。 with 6! / 4! / 2! - これは、私が今まで見たことのない二項係数を計算する別の方法のようです. 他の組み合わせも試してみましたが、両方の式は同じ数の組み合わせを生成します.あなたの問題は、二項係数の問題に変換できます。

これを考えると、二項係数を操作するための一般的な関数を処理するために私が書いたクラスを利用できるように見えます。

  1. 任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。この方法により、この種の問題を簡単に解決できます。

  2. K インデックスを、並べ替えられた二項係数テーブル内のエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的性質を使用して行われます。私の論文はこれについて語っています。この手法を発見して公開したのは私が最初だと思いますが、間違っている可能性があります。

  3. ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。

  4. Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。

  5. このクラスは .NET C# で記述されており、問題に関連するオブジェクト (存在する場合) をジェネリック リストを使用して管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を実行するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。

  6. クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

このクラスを選択した言語に変換するのは難しくありません。

非常に大きな N を使用しているため、プログラムが処理できるよりも大きな数が作成される可能性があるため、いくつかの制限がある場合があります。これは、K も大きくなる可能性がある場合に特に当てはまります。現在、クラスは int のサイズに制限されています。しかし、long を使用するように更新するのは難しくありません。

于 2012-09-25T11:21:57.240 に答える