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

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

2 голосов
/ 29 августа 2009

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

Проблема:

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

Ответы [ 2 ]

4 голосов
/ 29 августа 2009

Насколько я понимаю, вы фактически запрашиваете способы разбиения интервала [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,
0 голосов
/ 29 августа 2009

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

Обычно там 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} разделением).

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

...