順序付けられたパーティションセットのアルゴリズム

Question

トークンの入力セット（たとえば{a、b、c}）が与えられていると、入力要素の順序を考慮したパーティションのセットを与えるアルゴリズムを探しています。言い換えれば、私は順序を変えずにトークンのまわりに括弧を入れる可能性をすべて探しています。 {a,b,c}については

これは(ab)cd、a(bc)d、ab(cd)、(abc)d、a(bcd)、((ab)c)d、(a(bc))d、a((bc)d)、a(b(cd))（私はそれらすべてを持って願っています）になり{a,b,c,d}について(ab)cとa(bc)、

だろう。

これは、Bell Numberとやや関係がありますが、（ac）bのようなパーティションも考慮しているので大きすぎます。

CYK-Algorithmの派生でこの問題が解決する可能性があるという噂を聞いたことがありますが、CYKはCNF文法を解析するように設計されているため、これがどのように機能するのか分かりません。

(ab)cd 
a(bc)d 
ab(cd) 
(abc)d 
a(bcd) 

あなたは外側のループは、項目数のためのもの、forループ2とこれらを生成できます。

Answer 1

はセット{a,b,c,d}次のパーティションがあるためということは、トップレベルで、あなただけのパーティションとし括弧の内側（2からセット内の項目の数からマイナス1まで）の内側のループは、開始括弧の前の項目数に対応しています（0からセット内の項目数から括弧内の数字を引いたもの） 。したがって、上記の例では、外側のループは2から3までを反復し、内側のループは0から2まで、最初の時間は0から2まで繰り返されます。

これを実行すると、括弧内の項目を再帰的に分割して、完全なパーティションセットを取得するのはかなり簡単です。 1つのトリッキーな部分は、トップレベルでは、（明らかに）有効なパーティションとして角括弧なしのすべての項目を出力しないことですが、再帰するときにはそうすることです。ここで

は文字列でこれを行うにはJavaでいくつかの簡単なコードです：

public static void outputPartitions(String head, String partition, String tail, boolean top) 
{ 
    int len = partition.length(); 
    if(!top) // only output the items without brackets when not at the top level 
     System.out.println(head + partition + tail); 

    for(int i = 2; i <= len-1; i++) 
    { 
     for(int j = 0; j <= len-i; j++) 
     { 
      outputPartitions(head + partition.substring(0, j)+"(", 
       partition.substring(j, j+i), 
       ")"+partition.substring(j+i)+tail, false); 
     } 
    } 
} 

public static void main (String[] args) throws java.lang.Exception 
{ 
    outputPartitions("", "abcd", "", true); 
} 

出力：

(ab)cd 
a(bc)d 
ab(cd) 
(abc)d 
((ab)c)d 
(a(bc))d 
a(bcd) 
a((bc)d) 
a(b(cd)) 

Answer 2

すべての完全なカッコ（各括弧のペアはちょうど2つの要素が含まれている1）が可能それぞれのかっこのペアがノードであり、それに含まれる2つの要素がその子であるツリー構造と見なされます。たとえば(a((bc)d))については、次のとおりです。

() 
/\ 
a () 
/\ 
() d 
/\ 
b c 

そこで質問がされます。入力シーケンス与え、どのように多くのそのような木を構築することができますか？これは、ルートノード（aとbcdの間、abとcdの間、そしてabcとdの間の可能なすべての「スプリットポイント」）を試し、子シーケンスの分割点を再帰的に試すことで解消できます。

これは、matrix-chain multiplicationと密接に関連していることに注意してください。

Answer 3

この問題は面白いですし、私はこの問題を解決する有望なアルゴリズムをいくつか知られている他の解決策を楽しみにしています...一方、私は私の考えを伝えます。

私はあなたの順序集合はなく、 私は間違ってあなたの質問を理解していなかった場合、私は、単純な考えを持っているどのようなデータ構造を知らない：

を多分私達はただ従う

として再帰式で簡単なrecurssiveを使用することができます

Split(ordered set A){ 
    if(len(A) == 1) print(A[0]) 
    string group = ""; 
    for(int i in [1, len(A)]){ 
     group = group+" "+A[i]; 
     A remove A[i]; 
     print(group + "," + Split(A));  
    } 
} 

基本的に、それは最初の要素から最後の要素を、セットをループしている、各反復で、最初のパーティションとして最初i要素を取り、その後、（再帰）再び同じ関数を呼び出し、これらのiの要素を削除するには（あなたに依存しますデータ構造、あなたは必要ではないかもしれません物理的には削除されているが、セットの一部分だけを渡すととにかくそれがコンセプトです）

パフォーマンスはこのように遅いですが、すべての組み合わせを取得する必要があると考えています。

実際には、最初の4つの要素、または4つの連続した要素、またはセット内のどこにあっても4つの連続する要素について、パーティションのサイズを知る必要があります。それらはすべて同じ方法で分割することができます。だから我々は確かにのみ、動的プログラミングに上記再帰を強化することができn要素、とのセットを分割するためにすべての方法を保存する必要があります。

vector<vector<int>> pos[n]; 
// pos[i] is my way to store the "configuration" of the partition for i elements 
// for example: pos[7] may store [[1,3,7], [2,4,7]] 
// Means (1..1),(2..3),(4..7) is one way to partition 7 elements 
// (1..2),(3..4),(5..7) is another way 
// I want to find pos with this dynamic programming method 

Split(int size){ 
    if(pos[size] is not empty){ 
     return pos[size]; 
    } 
    if(size == 1){ 
     push [1] into pos; 
     return pos; 
    } 
    vector<vector<int>> ret; 
    for(int i in [1..n]){ 
     vector<vector<int>> subPartitions= Split(n-i); 
     for(vector<int> partition in [1..size(subPartitions)]){ 
      Add i (offset) to all element in partition 
      vector<int> newPartition = Merge([i], parition); 
      push newPartition to ret; 
     } 
    } 
    return pos[size] = ret; 
} 

それはハイレベルの概念的な擬似コードで、データ構造や実装に依存します許容可能なパフォーマンスで問題を解決する可能性があります。