На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Разбить множество на подмножества
    Здравствуйте, помогите пожалуйста, нужно разбить множество из n элементов на всеми способами k подмножеств
    например
    ввод n=3({1,2,3}), k = 2
    вывод
    {1}{2,3}
    {2}{1,3}
    {3}{1,2}
      Сама задача больше подходит для раздела Алгоритмы. Реализация на конкретном языке- это уже второе дело.

      Проще всего сгенерировать разбиения рекурсивно, опираясь на принцип получения чисел Стирлинга второго рода

      S(n, k) = S(n-1, k-1) + k * S(n-1, k)
      Сообщение отредактировано: MBo -
        Дополню MBo. Смысл формулы следующий - для получения всех разбиений из n элементов на k подмножеств мы можем взять:
        1) Взять все из (n-1, k-1) разбиений, и добавить n-ый элемент как новое подмножество. Это даёт первое слагаемое в формуле.
        2) Взять все (n-1, k) разбиений, и добавить n-ый элемент во все k подмножеств по очереди. Это - второе слагаемое.
          Цитата MBo @
          Сама задача больше подходит для раздела Алгоритмы. Реализация на конкретном языке- это уже второе дело.

          Проще всего сгенерировать разбиения рекурсивно, опираясь на принцип получения чисел Стирлинга второго рода

          S(n, k) = S(n-1, k-1) + k * S(n-1, k)

          а если нужно реализовать без рекурсии?
            >а если нужно реализовать без рекурсии?

            Можно завести таблицу (двумерный массив), содержащую наборы множеств для пар n/k, и заполнять её по строкам и рядам, используя тот же принцип.
            Сообщение отредактировано: MBo -
              Дели задачу на две. Основная задача - это представление числа n в виде k слагаемых ni. Подзадача - это деление множества на подмножества заданного размера n(k).
              Обе задачи - вполне стандартные. Первая вообще простейшая, вторая тоже проста, если в множестве нет повторяющихся элементов, неразличимых в подмножестве.
                Akina
                А что, первая задача разве двойственна второй? Или это предлагается как основа для размеров множеств? От последнего особой пользы не видно.
                  MBo
                  Пример у автора слишком простой. Давай чуть усложним.

                  n=4({1,2,3,4}), k = 2.
                  Тут возможны уже два варианта - подмножества из 3 и 1 элемента и подмножества из 2 элементов каждое. Вот тебе первая задача (представить число 4 в виде 2 слагаемых, целых, больше нуля).

                  Рассматриваем вариант 1-3. Возможные варианты: ({1},{2,3,4}); ({2},{1,3,4}); ({3},{1,2,4}); ({4},{1,2,3}).
                  Рассматриваем вариант 2-2. Возможные варианты: ({1,2},{3,4}); ({1,3},{2,4}); ({1,4},{2,3}).
                  Т.е. для каждого решения первой задачи решаем вторую.

                  В итоге - получаем полный набор решений.
                    Akina
                    ОК, посыл ясен.
                    Правда, при генерации мест и раскладывании по ним предметов уже для n=6-7 я когда-то сталкивался с главным цимесом - как разложить предметы по множествам без повторов. Решал как-то запутанно, с удалением-возвращением предметов (наверное, можно и проще).

                    Рекурсивное наращивание множеств решает это автоматически, и кода десятка два строк должно получиться

                    Есть ещё эффективный, но сложный метод последовательной генерации наборов подмножеств (может, даже в lex порядке) с использованием т.н. restricted-grow strings (RGS), но своего опыта в этом нет.
                      Цитата MBo @
                      как разложить предметы по множествам без повторов.

                      А эта задача решается в обратном порядке. Генерируется перестановка полного множества, потом она режется на части в соответствии с делением числа на слагаемые. Отсев дубликатов выполняется именно на стадии генерации перестановки.
                        Цитата MBo @
                        Правда, при генерации мест и раскладывании по ним предметов уже для n=6-7 я когда-то сталкивался с главным цимесом - как разложить предметы по множествам без повторов. Решал как-то запутанно, с удалением-возвращением предметов (наверное, можно и проще).

                        Вот +1. Правда, я фиксировал минимальные элементы в каждой корзине. Но в любом случае это не было так тривиально, как описывает Akina.

                        Цитата Akina @
                        А эта задача решается в обратном порядке. Генерируется перестановка полного множества, потом она режется на части в соответствии с делением числа на слагаемые. Отсев дубликатов выполняется именно на стадии генерации перестановки.

                        Можно подробнее? Например, пусть у нас n=4, k=2, и разбиение (2, 2). Можешь описать, как именно будут генерироваться перестановки?
                          Цитата OpenGL @
                          пусть у нас n=4, k=2, и разбиение (2, 2). Можешь описать, как именно будут генерироваться перестановки?

                          Генерим все перестановки 4 элементов, делим их на 2-2, и отсеиваем дубликаты. Признаки дубликатов:
                          1) Элементы блока расположены не в лексикографическом порядке
                          2) (для блоков равной длины) Лексикографически меньший блок идёт позже

                          12-34
                          12-43 (1 - блок 43 нарушает ЛГ-порядок)
                          13-24
                          13-42 (1)
                          14-23
                          14-32 (1)
                          21-34 (1)
                          21-43 (1)
                          23-14 (2 - блок 23 ЛГ больше, чем 14)
                          23-41 (1)
                          24-13 (2)
                          24-31 (1)
                          31-24 (1)
                          31-42 (1)
                          32-14 (1)
                          32-41 (1)
                          34-12 (2)
                          34-21 (1)
                          41-23 (1)
                          41-32 (1)
                          42-13 (1)
                          42-31 (1)
                          43-12 (1)
                          43-21 (1)
                          Сообщение отредактировано: Akina -
                            А, ну так не интересно :) Я думал, что есть простой алгоритм, позволяющий сгенерировать сразу без повторов. Например, в твоём алгоритме можно избавиться от значительной части их, если вместо массива множеств переставлять массив, построенный по разбиению числа n вида (n1 единиц, n2 двоек, ... nk k-шек), и элемент в i-той позиции будет показывать, к какому множеству относится i-ый элемент. Вероятно, к этому можно добавить ещё какое-то условие, чтобы генерировалось совсем без повторов.
                            Сообщение отредактировано: OpenGL -
                              OpenGL
                              Не-е-е... на самом деле этот алгоритм гораздо более затратный - но зато он простой для реализации и, главное, для понимания.
                              А решать задачу надо вторым способом - именно начинать с деления на слагаемые, а потом по этому делению рекурсивно строить разбиения, на каждом шаге рекурсии выделяя из текущего множества все подмножества заданного размера.
                                Akina, твой способ неплох, когда размер множеств и число подмножеств невелики. Для больших затраты растут слишком быстро. Метод, предложеннй MBo и OpenGL позволяет сгенерировать все нужные разбиения без повторов.

                                Добавлено
                                Причём алгоритму даже стек не нужен. Каждое разбиение можно сгенерировать по предыдущему.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0328 ]   [ 15 queries used ]   [ Generated: 28.03.24, 20:07 GMT ]