这个问题很有趣,我期待着其他人用一些已知的有前途的算法来解决这个问题……与此同时,我将提供我的想法。
我不知道你的有序集合是什么数据结构,但如果我没有误解你的问题,我有一个简单的想法:
也许我们可以只使用一个简单的递归,递归公式如下:
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];
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;
}
这是一个高级概念性的伪代码,根据数据结构和实现方式,它可以以可接受的性能解决您的问题。
abc
是{a,b,c}
的一个有效的划分吗?abcd
是{a,b,c,d}
的一个有效的划分吗?换句话说,输出不带括号的标记集合。 - samgak(ab)(cd)
怎么样? - Paul Hankin