Как найти все возможные не повторяющиеся пересечения множеств?
Мне нужно вычислить количество возможных комбинаций которые можно получить комбинируя множества (как я понимаю смесь из комбинаторики и декартово произведение). Я знаю, как вычислить число сочетаний без повторений для одного множества: n!/m!*(n-m)!, где n - количество элементов заданного множества, m - количество сочетаний (разрядов). Но если нужно скомбинировать несколько множеств?
Пример. Первое множество X={1,2,3}, второе множество Y={4,5}, третье множество Z={6,7}. Я хочу получить все возможные сочетания при одиночном, двойном и тройном комбинировании. Руками если считать получается (порядок в комбинации значения не имеет, повторов быть не должно, все элементы множеств уникальны):
Как я понимаю, общих элементов нет.
На примере 3-х множеств с мощностями a, b и c.
m=0: 1 комбинация
m=1: a + b + c комбинаций
m=2: a*b + b*c + a*c комбинаций
m=3: a*b*c комбинаций
Итого
1 + a + b + c + ab + bc + ca + abc
1 + a + b + ab + c*(1 + a + b + ab)
(1 + a + b + ab)(1 + c)
...
(1 + a)(1 + b)(1 + c)
На ваших данных получаем 4*3*3 = 36
Ответ подсказывает и принцип, как его посчитать. Из одного множества можно выбрать 1 + a способами: либо не берём (пустое множество), либо берём a способами.
Если добавить новое множество в рассмотрение, то либо мы из него не берём элемент, либо тоже берём, b способами, итого: (1+a)(1+b). Т.е. каждое множество Aᵢ даёт нам 1+|Aᵢ| новых вариантов, где |A| - мощность (кол-во элементов) множества A.
Т.о. ответ: ∏(1+|Aᵢ|)
Учтите, что эта формула учитывает так же и единственный вариант выбрать 0 элементов (результат - пустое множество), соот-но от того, что вы посчитали в вопросе отличается на единицу (36 вместо 35).
Объяснение относительно понятно, только не уловил, как в 1+|M| посчитать М. Можно пояснить на упрощенном примере двух множеств: X={1,2,3}, Y={4,5}? В моем понимании для разрядности 1 возможно 5 вариантов (ввиду уникальности элементов), для разрядности 2 их уже 3*2=6. И в итоге возможно 11 комбинаций.
|M| - мощность множества M, т.е. кол-во элементов. |X| = 3, |Y| = 2.
Итого по формуле 4*3 = 12. С учётом того, что формула берёт в расчет также и разрядность 0 (в коем случае всегда 1 вариант - пустое множество), получается тот же ответ, что и у вас.
Александр Ручкин: Так, т.е. для моего случая получается ∏(1+|Aᵢ|) - 1 (ввиду отсутствия разрядности 0). Проверил сейчас данные по другому набору множеств, действительно работает! Огромное спасибо! А в рамках какой дисциплины происходит изучение подобных задач? Т.е. где можно найти решение подобных задач (к примеру, если нужно будет посчитать в условии когда в комбинации будет учитываться положение в разрядах, т.е. {1,2} не тоже самое, что {2,1})?
Простой
