有序分区集的算法

Question

给定一组输入标记(例如 {a,b,c})，我正在寻找一种算法，该算法可为我提供一组符合输入元素顺序的分区。换句话说，我正在寻找在不更改顺序的情况下将标记放在括号中的所有可能性。

对于 {a,b,c} 这将是 (ab)c 和 a(bc),

对于 {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)) (我希望我得到了它们).

我认为这与 Bell Number 有某种关系，尽管它太大了，因为它也在考虑像 (ac)b 这样的分区。

我听说这个问题可以通过推导 CYK-Algorithm 来解决。尽管我不明白这应该如何工作，因为 CYK 旨在解析 CNF 语法。

Answer 1

假设您只在顶层进行分区，这意味着对于集合 {a,b,c,d} 您有以下分区:

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

您可以使用两个 for 循环生成这些，外层循环计算括号内的项目数(从 2 到集合中的项目数减 1)，内层循环计算之前的项目数左括号(从 0 到集合中的项目数减去括号内的数字)。因此，在上面的示例中，外循环从 2 迭代到 3(含)，内循环第一次从 0 迭代到 2(含)，第二次从 0 迭代到 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))