math - Algorithm for ordered set of partitions -

given input set of tokens (e.g. {a,b,c}), searching algorithm gives me set of partitions respects order of input elements. other words searching possibilities put brackets around tokens without changing order.

for {a,b,c} (ab)c , a(bc),

for {a,b,c,d} (ab)cd, a(bc)d, ab(cd), (abc)d, a(bcd), ((ab)c)d, (a(bc))d, a((bc)d), a(b(cd)) (i hope got them all).

i figure has somehow bell number, although large since considering partitions (ac)b well.

i heard rumors problem might solvable derivation of cyk-algorithm although not understand how should work, since cyk designed parse cnf grammars.

suppose partition @ top level, means set {a,b,c,d} have following partitions:

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

you can generate these 2 loops, outer loop being number of items inside brackets (from 2 number of items in set minus 1), , inner loop being number of items before opening bracket (from 0 number of items in set minus number inside brackets). in example above outer loop iterates 2 3 inclusive, , inner loop iterates 0 2 inclusive first time through , 0 1 second.

once have done it's pretty easy recursively partition items inside brackets full set of partitions. 1 tricky part @ top level, don't (apparently) want output items without brackets valid partition, when recurse do.

here simple code in java strings:

public static void outputpartitions(string head, string partition, string tail, boolean top) {     int len = partition.length();     if(!top) // output items without brackets when not @ top level         system.out.println(head + partition + tail);      for(int = 2; <= 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); } 

output:

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