有序分区的算法

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算法的推导来解决，尽管我不明白这应该如何工作，因为CYK是设计用于解析CNF语法的。

- mxcd

---

abc 是 {a,b,c} 的一个有效的划分吗？abcd 是 {a,b,c,d} 的一个有效的划分吗？换句话说，输出不带括号的标记集合。 - samgak

(ab)(cd)怎么样？ - Paul Hankin

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))

- samgak

Answer 2

每个完整的括号结构（每个括号对只包含两个元素）可以被视为一棵树形结构，其中每个括号对是一个节点，它所包含的两个元素是其子节点。例如(a((bc)d))，可以表示为：

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

问题是：给定输入序列，可以构造多少这样的树？这可以通过尝试所有可能的根节点“分裂点”（在a和bcd之间，在ab和cd之间，在abc和d之间）来回答，并递归地尝试子序列的分裂点。

请注意，这与矩阵链乘法密切相关。

- Aasmund Eldhuset

Answer 3

这个问题很有趣，我期待着其他人用一些已知的有前途的算法来解决这个问题……与此同时，我将提供我的想法。

我不知道你的有序集合是什么数据结构，但如果我没有误解你的问题，我有一个简单的想法：

也许我们可以只使用一个简单的递归，递归公式如下：

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 个元素，再次调用相同的函数（递归）（根据您的数据结构，您可能不需要物理删除，而只需传递一部分集合 A，无论如何，这是概念）。

这种方式的性能较慢，但考虑到您必须获取所有组合，我认为这可能是可以接受的。

您可以通过一些方法加速此过程：实际上，我们只需要知道集合的大小即可获得分区，对于前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;
}

这是一个高级概念性的伪代码，根据数据结构和实现方式，它可以以可接受的性能解决您的问题。

- shole