Комбинаторика:Создание 10 групп по 100 элементов, при этом элементы остаются отсортированными

Question

У меня проблема, связанная с комбинаторикой.К сожалению, я не могу описать это абстрактно, поэтому я пытаюсь объяснить это как историю.:)

Проблема:

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 было бы лучшим, но я был бы рад увидеть решения и на других языках.:)

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,

Answer 2

Мне нужны все возможные решения для этих групп, поскольку найти одно созвездие несложно.

Обычно их там 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 х 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}).

С этого момента вы должны быть в состоянии представить себе общую схему нужного вам алгоритма - то есть, если вы хотите решить задачу написания этой функции с нуля.Другие люди уже сделали это написано множество эффективных функций легко решить проблему.