php - 组合学:构建 10 组，每组 100 个元素，同时元素保持排序

Question

我有一个关于组合学的问题。不幸的是，我无法抽象地描述它，所以我尝试用一​​个故事来解释它。 :)

问题:

1. 校园里有 100 名 child 。
2. 它们都有独特的高度，假设值为 100-199 厘米。
3. 您想要建立 10 个小组，每个小组由 1-99 名 child 组成。
4. 如何构建所有组，而 child 必须按高度排序？
5. 我需要针对这些群体的所有可能的解决方案，因为找到一个星座并不难。

简短易懂:

所有 100 名 child 并排站立。您只需决定在哪里将它们分组并找到所有解决方案。

示例(值为高度):

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] 不可能

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] 有可能

希望你能帮助我。预先非常感谢您!

PS:这不是作业。 ;)通常，我需要一个用数字来完成此操作的函数。但我无法像“在所有数字都已排序的情况下构建 k 组数字”一样抽象地描述这一点。我以为这样你就不会明白。 :) PHP 中的解决方案是最好的，但我也很高兴看到其他语言的解决方案。 :)

Answer 1

据我了解，您实际上是在寻求将区间 [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,