Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.235.75.229] |
|
Сообщ.
#1
,
|
|
|
Здравствуйте, помогите пожалуйста, нужно разбить множество из n элементов на всеми способами k подмножеств
например ввод n=3({1,2,3}), k = 2 вывод {1}{2,3} {2}{1,3} {3}{1,2} |
Сообщ.
#2
,
|
|
|
Сама задача больше подходит для раздела Алгоритмы. Реализация на конкретном языке- это уже второе дело.
Проще всего сгенерировать разбиения рекурсивно, опираясь на принцип получения чисел Стирлинга второго рода S(n, k) = S(n-1, k-1) + k * S(n-1, k) |
Сообщ.
#3
,
|
|
|
Дополню MBo. Смысл формулы следующий - для получения всех разбиений из n элементов на k подмножеств мы можем взять:
1) Взять все из (n-1, k-1) разбиений, и добавить n-ый элемент как новое подмножество. Это даёт первое слагаемое в формуле. 2) Взять все (n-1, k) разбиений, и добавить n-ый элемент во все k подмножеств по очереди. Это - второе слагаемое. |
Сообщ.
#4
,
|
|
|
Цитата MBo @ Сама задача больше подходит для раздела Алгоритмы. Реализация на конкретном языке- это уже второе дело. Проще всего сгенерировать разбиения рекурсивно, опираясь на принцип получения чисел Стирлинга второго рода S(n, k) = S(n-1, k-1) + k * S(n-1, k) а если нужно реализовать без рекурсии? |
Сообщ.
#5
,
|
|
|
>а если нужно реализовать без рекурсии?
Можно завести таблицу (двумерный массив), содержащую наборы множеств для пар n/k, и заполнять её по строкам и рядам, используя тот же принцип. |
Сообщ.
#6
,
|
|
|
Дели задачу на две. Основная задача - это представление числа n в виде k слагаемых ni. Подзадача - это деление множества на подмножества заданного размера n(k).
Обе задачи - вполне стандартные. Первая вообще простейшая, вторая тоже проста, если в множестве нет повторяющихся элементов, неразличимых в подмножестве. |
Сообщ.
#7
,
|
|
|
Akina
А что, первая задача разве двойственна второй? Или это предлагается как основа для размеров множеств? От последнего особой пользы не видно. |
Сообщ.
#8
,
|
|
|
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}). Т.е. для каждого решения первой задачи решаем вторую. В итоге - получаем полный набор решений. |
Сообщ.
#9
,
|
|
|
Akina
ОК, посыл ясен. Правда, при генерации мест и раскладывании по ним предметов уже для n=6-7 я когда-то сталкивался с главным цимесом - как разложить предметы по множествам без повторов. Решал как-то запутанно, с удалением-возвращением предметов (наверное, можно и проще). Рекурсивное наращивание множеств решает это автоматически, и кода десятка два строк должно получиться Есть ещё эффективный, но сложный метод последовательной генерации наборов подмножеств (может, даже в lex порядке) с использованием т.н. restricted-grow strings (RGS), но своего опыта в этом нет. |
Сообщ.
#10
,
|
|
|
Цитата MBo @ как разложить предметы по множествам без повторов. А эта задача решается в обратном порядке. Генерируется перестановка полного множества, потом она режется на части в соответствии с делением числа на слагаемые. Отсев дубликатов выполняется именно на стадии генерации перестановки. |
Сообщ.
#11
,
|
|
|
Цитата MBo @ Правда, при генерации мест и раскладывании по ним предметов уже для n=6-7 я когда-то сталкивался с главным цимесом - как разложить предметы по множествам без повторов. Решал как-то запутанно, с удалением-возвращением предметов (наверное, можно и проще). Вот +1. Правда, я фиксировал минимальные элементы в каждой корзине. Но в любом случае это не было так тривиально, как описывает Akina. Цитата Akina @ А эта задача решается в обратном порядке. Генерируется перестановка полного множества, потом она режется на части в соответствии с делением числа на слагаемые. Отсев дубликатов выполняется именно на стадии генерации перестановки. Можно подробнее? Например, пусть у нас n=4, k=2, и разбиение (2, 2). Можешь описать, как именно будут генерироваться перестановки? |
Сообщ.
#12
,
|
|
|
Цитата 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) |
Сообщ.
#13
,
|
|
|
А, ну так не интересно Я думал, что есть простой алгоритм, позволяющий сгенерировать сразу без повторов. Например, в твоём алгоритме можно избавиться от значительной части их, если вместо массива множеств переставлять массив, построенный по разбиению числа n вида (n1 единиц, n2 двоек, ... nk k-шек), и элемент в i-той позиции будет показывать, к какому множеству относится i-ый элемент. Вероятно, к этому можно добавить ещё какое-то условие, чтобы генерировалось совсем без повторов.
|
Сообщ.
#14
,
|
|
|
OpenGL
Не-е-е... на самом деле этот алгоритм гораздо более затратный - но зато он простой для реализации и, главное, для понимания. А решать задачу надо вторым способом - именно начинать с деления на слагаемые, а потом по этому делению рекурсивно строить разбиения, на каждом шаге рекурсии выделяя из текущего множества все подмножества заданного размера. |
Сообщ.
#15
,
|
|
|
Akina, твой способ неплох, когда размер множеств и число подмножеств невелики. Для больших затраты растут слишком быстро. Метод, предложеннй MBo и OpenGL позволяет сгенерировать все нужные разбиения без повторов.
Добавлено Причём алгоритму даже стек не нужен. Каждое разбиение можно сгенерировать по предыдущему. |