2

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

问题：

  1. 校园里有100个孩子。
  2. 假设值为 100-199 厘米，它们都有独特的高度。
  3. 你想建立 10 个小组，每个小组由 1-99 个孩子组成。
  4. 当孩子们必须按身高排序时，你怎么能建立所有的组？
  5. 我需要为这些群体提供所有可能的解决方案，因为找到一个星座并不难。

简短易懂：

所有100个孩子并排站立。您只需要决定在哪里将它们分成组并为此找到所有解决方案。

示例（值是高度）：

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

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

我希望你能帮助我。非常感谢您！

PS：这不是家庭作业。;) 通常，我需要一个函数来处理数字。但是我不能像“在对所有数字进行排序的同时构建 k 组数字”那样抽象地描述这一点。我以为你不会这样理解。:) PHP 的解决方案是最好的，但我也很高兴看到其他语言的解决方案。:)

4

2 回答 2

4

据我了解，您实际上是在寻求将区间 [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,
于 2009-08-29T16:51:10.880 回答
0

我需要为这些群体提供所有可能的解决方案，因为找到一个星座并不难。

通常，有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 个项目的集合，这很容易通过使用费雷尔图进行枚举。

我可以通过将数字 20 划分为 3 个桶来演示费雷尔图：从 20 col 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} 不同的分区）。

从这一点开始，您应该能够设想出您需要的算法的大致轮廓——也就是说，如果您想要从头开始编写这个函数的挑战。其他人已经编写了许多有效的函数来轻松解决问题。

于 2009-08-29T17:52:55.687 回答