1次元配列のすべてのk-パーティションをN個の要素で列挙しますか？

Question

これは簡単なリクエストのようですが、Googleでは自分の友人ではありません。なぜなら、「パーティション」はデータベースとファイルシステムの領域でヒットしているからです。

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

、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、それが後に（kが成長すると）以前の結果を利用すれば素晴らしいでしょう。

リンクがある場合は、お気軽にお申し込みください。

Answer 1

（kの値が小さいほど）以前の結果を再利用するために、再帰を行うことができます。

このようなパーティション化を終了インデックスのリストと考えてください（パーティションの開始インデックスは最後のパーティションの終了インデックスにすぎないか、最初のインデックスの0になります）。

ので、パーティショニングのあなたのセットが0とN.

間k非減少整数のすべての配列のセットだけ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に無制限の場合は、再帰的に行うことができます。

S及びEをすることにより得られるインデックス間kパーティションの組の各値についてS及びEの間のEFP "最初のパーティションの終わりを" ルーピング

• ：

  • 再帰的にEFPとSの間のk-1パーティションのリストを見つける

  • そのリスト内の各ベクトルについて、そのベクトルに "EFP"をプリペンドします。

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

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

Answer 2

各パーティションは、パーツを分けるk-1インデックスによって記述することができます。順序は保持されるので、これらのインデックスは非減少でなければなりません。つまり、サイズk-1のサブセットと求めるパーティションとの間に直接の対応があります。

How to iteratively generate k elements subsets from a set of size n in java?

だけしわが空の部分が許可されている場合、いくつかのカットポイントを一致させることができるということですが、：

サイズk-1のすべてのサブセットを反復処理するために、あなたは質問をチェックアウトすることができますサブセットには各インデックスを1回まで含めることができます。あなたは置き換えることで、わずかにアルゴリズムを調整する必要があります：

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

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