组合学:构建 10 组,每组 100 个元素,同时元素保持排序
-
20-09-2019 - |
题
我有一个关于组合学的问题。不幸的是,我无法抽象地描述它,所以我尝试用一个故事来解释它。:)
问题:
- 校园里有 100 个孩子。
- 它们都有独特的高度,假设值为 100-199 厘米。
- 您想要建立 10 个小组,每个小组由 1-99 名儿童组成。
- 当孩子们必须按身高排序时,如何才能建立所有的小组呢?
- 我需要为这些群体提供所有可能的解决方案,因为找到一个星座并不难。
简短易懂:
100 个孩子全部并排站着。您只需决定在哪里将它们分组并找到所有解决方案。
示例(值为高度):
[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] 不可能
[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] 是可能的
我希望你可以帮助我。预先非常感谢您!
附:这不是家庭作业。;)通常,我需要一个用数字来完成此操作的函数。但我无法像“在所有数字都已排序的情况下构建 k 组数字”一样抽象地描述这一点。我以为这样你就不会明白。:) PHP 中的解决方案是最好的,但我也很高兴看到其他语言的解决方案。:)
解决方案
据我了解,您实际上是在寻求将区间 [100,199] 分为 10 个部分的方法,即您想要找到数字 x[0], ..., x[10] 使得:
x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199
定义递归函数 partition(intervalSize, pieces)
它计算划分给定区间的方法数量。你在追随 partition(100, 10)
.
以下 Java 代码计算分区数(抱歉,不太了解 PHP):
public class Partitions
{
static long[][] partitions = new long[100][10];
private static long partition(int intervalSize, int pieces)
{
if (partitions[intervalSize-1][pieces-1] != 0) {
return partitions[intervalSize-1][pieces-1];
}
long partition = 0L;
if (pieces == 1) {
partition = 1L;
} else {
for (int i = 1; i <= intervalSize - 1; i++) {
partition += partition(intervalSize - i, pieces - 1);
}
}
partitions[intervalSize-1][pieces-1] = partition;
return partition;
}
public static void main(String[] args)
{
System.out.println(partition(100, 10));
}
}
以下 Java 代码打印出实际的分区。由于 (100,10) 的分区数量非常高,因此我将说明 (5,3) 的答案:
public class Partitions2
{
private static void showPartitions(int sizeSet, int numPartitions)
{
showPartitions("", 0, sizeSet, numPartitions);
}
private static void showPartitions(String prefix, int start, int finish,
int numLeft)
{
if (numLeft == 0 && start == finish) {
System.out.println(prefix);
} else {
prefix += "|";
for (int i = start + 1; i <= finish; i++) {
prefix += i + ",";
showPartitions(prefix, i, finish, numLeft - 1);
}
}
}
public static void main(String[] args)
{
showPartitions(5, 3);
}
}
输出是:
|1,|2,|3,4,5, |1,|2,3,|4,5, |1,|2,3,4,|5, |1,2,|3,|4,5, |1,2,|3,4,|5, |1,2,3,|4,|5,
其他提示
我需要这些组的所有可能解决方案,因为不难找到一个星座。
一般情况下,有100个!排列 100 个项目的方法,但由于您保持顺序,因此可以缩小问题规模 实质上. 。你所描述的是一个 整数划分问题. 。例如,假设您将数字 5 划分为所有可能的整数子集,总和为 5,您将得到集合 {5}, {4, 1}, {3, 2}, {3, 1, 1 ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}。
整数分区的数量随着整数的大小呈指数增长,但指数增长足够慢,您可以枚举 n = 100 的所有分区,因为它们只有 190,569,292 个。这里的附加约束是,您希望过滤所有分区以获取恰好包含 10 个项目的集合,这可以通过使用 Ferrer 图轻松枚举。
我可以通过将数字 20 分为 3 个桶来演示费雷尔图:从 20 列 x 3 行网格开始,如下所示:
12345678901234567890 1****************** 2* 3*
所以,第一个分区是 {18, 1, 1}
现在将一个项目从堆栈顶部移动到下一个插槽中:
12345678901234567890 1***************** 2** 3*
我们的新分区是{17,2,1}。我们可以将另一项从一个堆栈移到另一个堆栈:
12345678901234567890 1**************** 2*** 3*
现在我们有 {16, 3, 1}。继续以这种方式,直到枚举完所有排列(由您决定 {17, 1, 2} 是否是与 {17, 2, 1} 不同的分区)。
从这一点来看,您应该能够设想所需算法的总体轮廓 - 也就是说,如果您愿意接受从头开始编写此函数的挑战。其他人已经 编写了很多高效的函数 轻松解决问题。