Задача о разбиении множества

@veniamin · Регистрация: 03.05.2016

Студворк — интернет-сервис помощи студентам

Доброго времени суток.

Хочется сформулировать алгоритм решения следующей задачи.

Дано множество из N различных элементов. Также дан некоторый набор его подмножеств. Надо выделить из этого набора разбиение множества, т.е. такой другой набор подмножеств, которые бы не персекались и их объединение равнялось бы исходному множеству. Либо показать, что решения нет. Если решений несколько, годится любое.

Я уже решил задачу лобовым пербором, но всё упирается в производительность. Интересует более эффективный путь. Может быть, есть какие-то готовые библиотеки по комбинаторике и теории множеств и.т.п.?

@ProgJ · 03.05.2016, 23:38

Тут вроде бы так можно поступить
1. Исключаем все подмножества имеющие элементы не из множества
2. Берем первый элемент множества. Перебираем все подмножества, имеющие этот элемент. Для каждого формируем новое множество вычитанием выбранного подмножества, с этим множеством проделываем шаги 1 и 2

@Shamil1 · 04.05.2016, 00:22

Сообщение от veniamin

Надо выделить из этого набора разбиение множества

Что такое разбиение, я знаю. А что такое разбиение, выделенное из набора подмножеств?

@veniamin · 04.05.2016, 13:45 **[ТС]**

Спасибо за ответы.

Для Shamil1:

Дан набор подмножеств множества. Разных, может быть пересекающихся, не обязательно всех возможных. Нужно отобрать из них те, что формируют разбиение.

Для ProgJ:

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

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

@ProgJ · 04.05.2016, 15:51

Сообщение от veniamin

насчёт пункта 1 - в подмножествах не может быть элемента не из исходного множества, это же подмножества.

если множество совпадает с полным множеством, то да
но когда вы выберете одно из подмножеств и вычтите его, новое множество уже не будет полным и пункт 1 пригодится

@veniamin · 04.05.2016, 15:58 **[ТС]**

Сообщение от ProgJ

если множество совпадает с полным множеством, то да
но когда вы выберете одно из подмножеств и вычтите его, новое множество уже не будет полным и пункт 1 пригодится

Теперь понятно, я это конечно учёл.

@Shamil1 · 04.05.2016, 17:26

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
import Data.Set (size, union)
import Data.List (sort)
 
find_partition n subsets = findp $ sort subsets
    where 
    findp [] = False
    findp [x] = size x == n
    findp (x:y:xs) 
        | size x == n = True
        | otherwise = xyOk && (findp (xy:xs)) || (findp (x:xs)) || (findp (y:xs))
            where 
            xy = union x y  
            xyOk = size xy == size x + size y

Добавлено через 1 минуту
Предлагаю:
1. перебирать подмножества, а не элементы
2. складывать (объединять) их, а не вычитать

Добавлено через 33 минуты
Первый вариант возвращал true/false. Вот вариант, который запоминает, как строится требуемый набор подмножеств.

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import Data.Set (size, union, Set)
import Data.List (sort)
 
find_partition n subsets = findp (sort subsets) [head subsets]
    where 
    findp [] zs       = []
    findp [x] zs      = if size x == n then zs else []
    findp (x:y:xs) zs = if size x == n then zs 
        else if xyOk && xyp /= [] then xyp
        else if xp /= [] then xp else yp
            where 
            xy   = union x y  
            xyOk = size xy == size x + size y
            xyp  = findp (xy:xs) (y:zs)
            xp   = findp (x:xs) zs
            yp   = findp (y:xs) [y]

Кратко суть:
1. сортируем список подмножеств по убыванию размера
2. условие выхода
2.1. список подмножеств пустой (неудача)
2.2. размер первого подмножества равен размеру множества (успех)
3. пробуем рекурсивно для нового списка:
3.1. заменяем первые два подмножества на их объединение (если они не пересекаются)
3.2. отбрасываем второе подмножество
3.3. отбрасываем первое подмножество

@veniamin · 06.05.2016, 13:50 **[ТС]**

Спасибо за подробный ответ. Правда, я Хаскель не знаю и не всё понял. В любом случае, с практической точки зрения я проблему решил. У меня тоже перебор шёл по подмножествам. При это я в цикле генерировал цепочки непересекающихся подмножеств, пока одна из них не оказывалась равной исходному множеству. Причёт рассматривались все варианты цепочек, в том числе отличающиеся только нумерацией. Я убал все лишние перестановки, и количество вариантов сократилось на 3 порядка. Не знаю на счёт теоретической сложности алгоритма, но на моих тестовых примерах всё работает почти мгновенно.

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@veniamin 0 / 0 / 0 Регистрация: 03.05.2016 Сообщений: 4

	Задача о разбиении множества 03.05.2016, 17:14. Показов 2009. Ответов 7 Метки нет (Все метки) Доброго времени суток. Хочется сформулировать алгоритм решения следующей задачи. Дано множество из N различных элементов. Также дан некоторый набор его подмножеств. Надо выделить из этого набора разбиение множества, т.е. такой другой набор подмножеств, которые бы не персекались и их объединение равнялось бы исходному множеству. Либо показать, что решения нет. Если решений несколько, годится любое. Я уже решил задачу лобовым пербором, но всё упирается в производительность. Интересует более эффективный путь. Может быть, есть какие-то готовые библиотеки по комбинаторике и теории множеств и.т.п.? 0

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	03.05.2016, 23:38
	Тут вроде бы так можно поступить 1. Исключаем все подмножества имеющие элементы не из множества 2. Берем первый элемент множества. Перебираем все подмножества, имеющие этот элемент. Для каждого формируем новое множество вычитанием выбранного подмножества, с этим множеством проделываем шаги 1 и 2 0

@veniamin 0 / 0 / 0 Регистрация: 03.05.2016 Сообщений: 4
	04.05.2016, 13:45 [ТС]
	Спасибо за ответы. Для Shamil1: Дан набор подмножеств множества. Разных, может быть пересекающихся, не обязательно всех возможных. Нужно отобрать из них те, что формируют разбиение. Для ProgJ: насчёт пункта 1 - в подмножествах не может быть элемента не из исходного множества, это же подмножества. За исключением этого пункта получается лобовой перебор. Я такое сделал, хочется что-то более вычислительно эффективное. А если это невозможно, может быть есть готовая реализация таких вещей, уже отлаженная и максимально быстрая. Добавлено через 3 минуты Хочу ещё заметить, что просто задача о построении разбиения множества, или всех его разбиений, решена кучу раз, имеется и готовый код в библиотеках по комбинаторике. Хочется решить эту задачу в модифицированном виде, когда набор элементов разбиения ограничен и известен заранее. 0

@veniamin 0 / 0 / 0 Регистрация: 03.05.2016 Сообщений: 4
	06.05.2016, 13:50 [ТС]
	Спасибо за подробный ответ. Правда, я Хаскель не знаю и не всё понял. В любом случае, с практической точки зрения я проблему решил. У меня тоже перебор шёл по подмножествам. При это я в цикле генерировал цепочки непересекающихся подмножеств, пока одна из них не оказывалась равной исходному множеству. Причёт рассматривались все варианты цепочек, в том числе отличающиеся только нумерацией. Я убал все лишние перестановки, и количество вариантов сократилось на 3 порядка. Не знаю на счёт теоретической сложности алгоритма, но на моих тестовых примерах всё работает почти мгновенно. 0