组合学：建立10组100个元素的组，同时保持元素的排序 [英] Combinatorics: Building 10 groups of 100 elements while elements remain sorted
问题描述
我遇到了有关组合学的问题。不幸的是，我无法抽象地描述它，因此我尝试将其解释为一个故事。 ：）
I've got a problem concerning combinatorics. Unfortunately, I can't describe it abstractly so I try to explain it as a story. :)
问题：
- 有校园里有100个孩子。
- 假设值在100-199厘米之间，它们都有独特的高度。
- 您想建立10个小组，每个小组由1-99个孩子组成。
- 当孩子必须按其身高排序时，如何建立所有组？
- 我需要所有可能的方法这些群体的解决方案，因为它并不难找到一个星座。
- There are 100 children on the schoolyard.
- They all have unique heights, assuming the values are 100-199cm.
- You want to build 10 groups, each consisting of 1-99 children.
- How can you build all the groups while the children must be sorted by their height?
- I need all possible solutions for these groups since it isn't hard to find one constellation.
简短易懂：
所有100个孩子并排站立。您只需决定将它们分成几组，并为此找到所有解决方案。
All 100 children stand side by side. You only have to decide where to split them into groups and find all solutions for this.
示例（值是高度）：
[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] 是不可能的
[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] is not possible
[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] 有可能
[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] is possible
我希望您能帮助我。
PS：这不是功课。 ;）通常，我需要一个使用数字执行此操作的函数。但是，我无法像在对所有数字进行排序时建立k个数字组这样的抽象描述。我以为你不会这样理解。 :)用PHP解决方案是最好的，但是我也很高兴看到其他语言的解决方案。 ：）
PS: It's no homework. ;) Normally, I need a function which does this with numbers. But I couldn't describe this abstractly like "building k groups of numbers while all numbers are sorted". I thought you wouldn't understand it this way. :) A solution in PHP would be best but I would be glad to see solutions in other languages as well. :)
推荐答案
据我所知，您实际上是在寻求将间隔[100,199]分为10个部分的方法，即您要查找数字x [0]，...，x [10]，使得：
As I understand it, you are effectively asking for ways of partitioning the interval [100,199] into 10 parts, i.e. you want to find numbers x[0], ..., x[10] such that:
x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199
定义递归函数 partition（intervalSize，piece ）计算分配给定间隔的方法的数量。您在 partition（100，10）之后。
Define a recursive function partition(intervalSize, pieces) which counts the number of ways to partition a given interval. You are after partition(100, 10).
以下Java代码对分区进行计数（对不起，请t非常了解PHP）：
The following Java code counts the partitions (sorry, don't know PHP that well):
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）的答案：
The following Java code prints out the actual partitions. Because the number of partitions is so high for (100,10), I'm illustrating the answer for (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,
这篇关于组合学：建立10组100个元素的组，同时保持元素的排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
