7

これは単純な要求のように思えますが、「パーティション」はデータベースとファイルシステムのスペースで多数のヒットを記録するため、Google は私の友人ではありません。

N 値 (N は定数) の配列のすべてのパーティションを k サブ配列に列挙する必要があります。サブ配列はまさにそれです-開始インデックスと終了インデックス。元の配列の全体的な順序は保持されます。

たとえば、N=4 で k=2 の場合:

[ | a b c d ] (0, 4)
[ a | b c d ] (1, 3)
[ a b | c d ] (2, 2)
[ a b c | d ] (3, 1)
[ a b c d | ] (4, 0)

k=3 の場合:

[ | | a b c d ] (0, 0, 4)
[ | a | b c d ] (0, 1, 3)
  :
[ a | b | c d ] (1, 1, 2)
[ a | b c | d ] (1, 2, 1)
  :
[ a b c d | | ] (4, 0, 0)

これは元の問題ではないと確信しています (いや、宿題ではありません) が、すべての k <= N に対して実行したいと思います。 ) 以前の結果を利用しました。

リンクがある場合は、共有してください。

4

2 に答える 2

7

以前の結果を再利用するために（の値が小さい場合k）、再帰を実行できます。

このようなパーティショニングは、終了インデックスのリストと考えてください（任意のパーティションの開始インデックスは、最後のパーティションの終了インデックス、または最初のパーティションの0です）。

kしたがって、パーティショニングのセットは、0からNまでの非減少整数のすべての配列のセットにすぎません。

kが制限されている場合は、kネストされたループを介してこれを行うことができます

for (i[0]=0; i[0] < N; i[0]++) {
    for (i[1]=i[0]; i[1] < N; i[1]++) {
    ...
            for (i[10]=i[9]; i[10] < N; i[10]++) {
                push i[0]==>i[10] onto the list of partitionings.
            }
    ...
    }
}

が無制限の場合k、再帰的に実行できます。

kインデックスSとEの間のパーティションのセットは、次の方法で取得されます。

  • SとEの間で「最初のパーティションの終わり」EFPをループします。各値について：

    • k-1EFPとSの間のパーティションのリストを再帰的に検索します

    • そのリスト内の各ベクトルについて、そのベクトルの前に「EFP」を追加します。

    • 結果の長さのベクトルがk結果のリストに追加されます。

私の答えは、各スライスのエンドポイントのリストを生成することに注意してください。（例が示すように）各スライスの長さのリストが必要な場合は、現在のスライスの端から最後のスライスの端を引いて長さを取得する必要があります。

于 2010-12-30T15:25:19.043 に答える
1

各パーティションは、パーツを区切るk-1インデックスで記述できます。順序が保持されるため、これらのインデックスは減少しない必要があります。つまり、サイズk-1のサブセットと、求めるパーティションの間には直接的な対応関係があります。

サイズk-1のすべてのサブセットを反復処理するには、次の質問を確認できます。

Javaでサイズnのセットからk個の要素のサブセットを繰り返し生成するにはどうすればよいですか？

唯一の問題は、空のパーツが許可されている場合、複数のカットポイントが一致する可能性があることですが、サブセットには各インデックスを最大で1回含めることができます。以下を置き換えることにより、アルゴリズムをわずかに調整する必要があります。

        processLargerSubsets(set, subset, subsetSize + 1, j + 1);

に

        processLargerSubsets(set, subset, subsetSize + 1, j);
于 2010-12-30T15:27:54.077 に答える