种群分割算法

Question

我有50个有序整数(1,2,3，..,50)，我寻找一种通用的方法将它分割成"n“方式("n”是保持元素顺序的从1到25的截止点的数目)。

例如，对于n=1 (一个临界点)，有49种可能的分组替代品(1,2-49，1-2,3-50，1-3,4-50，.)。对于n=2 (两个临界点)，分组选择如下: 1,2,3-50，1,2-3,4-50，.

你能推荐一些通用的算法来高效地完成这个任务吗？

谢谢，克里斯

谢谢大家的反馈。我审查了您的所有评论，我正在研究一个通用解决方案，它将返回所有组合(例如，1，2，3，4-50，1,2-3,4-50，.)所有数量的截止点。

再次谢谢你，克里斯

Answer 1

设序列长度为N，切片数为n。

当您注意到选择n个切片等同于从n - 1可能的拆分点中选择N - 1 (在序列中的每两个数字之间有一个拆分点)时，这个问题就变得更容易了。因此，有(n-1选择n-1)这样的切片。

要生成所有切片(到n片)，必须从n - 1生成所有1 to N - 1元素子集。

这个问题的精确算法放在这里：如何迭代地从一组大小为n的java中生成k元素子集？

Answer 2

你需要断奶，还是你只是数数。如果你只想数数，那就很简单了：

1截止= (n-1)选项

2截断= (n-1)*(n-2)/2选项

3截断= (n-1)(n-2)(n-3)/4选项

你可以看到这里的图案

如果你真的需要割断，那么你必须做循环，但是因为n太小了，埃米利奥是对的，只是用蛮力强迫它。

1个截止点

for(i=1,i<n;++i)
  cout << i;

2断头

for(i=1;<i<n;++i)
  for(j=i+1,j<n;++j)
    cout << i << " " << j;

3切断

for(i=1;<i<n;++i)
  for(j=i+1,j<n;++j)
    for(k=j+1,k<n;++k)
      cout << i << " " << j << " " << k;

再一次，你可以看到模式

Answer 3

所以你想从49个选择中选择25个分裂点，以所有可能的方式。有很多著名的算法可以这么做。

我想提请你注意这个问题的另一面。有49！/(25*(49-25)！)= 63 205 303 218 876 >= 2^45 ~= 10^13不同的组合。因此，如果您想要存储它，所需的内存量为32 to *sizeof of (组合)。我想它将超过1PB标记。

现在假设您希望动态地处理生成的数据。让我们用乐观假设每秒可以处理100万个组合(这里我假设没有并行化)。所以这个任务需要10^7秒= 2777小时= 115天。

这个问题比乍看上去复杂得多。如果你想在合理的时间内在家里解决问题，我的建议是改变策略，或者等待量子计算机的发展。