组合：构建10组100个元素，同时元素保持排序

Question

I've got a problem concerning combinatorics. Unfortunately, I can't describe it abstractly so I try to explain it as a story. :)

Problem:

1. There are 100 children on the schoolyard.
2. They all have unique heights, assuming the values are 100-199cm.
3. You want to build 10 groups, each consisting of 1-99 children.
4. How can you build all the groups while the children must be sorted by their height?
5. I need all possible solutions for these groups since it isn't hard to find one constellation.

Short and easy:

All 100 children stand side by side. You only have to decide where to split them into groups and find all solutions for this.

Example (values are the heights):

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] is not possible

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] is possible

I hope you can help me. Thank you very much in advance!

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. :)

Answer 1

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

Define a recursive function partition(intervalSize, pieces) which counts the number of ways to partition a given interval. You are after partition(100, 10).

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));     
    }

}

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);
    }
}

The output is:

|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,