Как подсчитать общее количество всех возможных уникальных подмножеств из набора с повторами?

Учитывая множество** S, содержащее повторяющиеся элементы, как можно определить общее количество всех возможных подмножеств S, где каждое подмножество уникально.

Например, пусть S = {A, B, B} и пусть K будет множеством всех подмножеств, тогда K = {{}, {A}, {B}, {A, B}, {B, B}, {A, B, B}} и, следовательно, |K| = 6.

Другой пример: если S = ​​{A, A, B, B}, то K = {{}, {A}, {B}, {A, B}, {A, A}, {B, B}, {A, B, B}, {A, A, B}, {A, A, B, B}} и, следовательно, |K| = 9

Легко видеть, что если S — вещественное множество, имеющее только уникальные элементы, то |K| = 2^|S|.

По какой формуле вычислить это значение |K| учитывая «набор» S (с дубликатами), не создавая все подмножества?

** Технически это не набор.


set counting math combinatorics language-agnostic
person Nixuz    schedule 10.04.2009    source источник
comment
Это действительно математический вопрос, а не вопрос программирования.   -  person Eddie    schedule 10.04.2009
comment
Это проблема, связанная с программированием, которая у меня есть, и такая формула важна для анализа времени работы определенных алгоритмов, связанных с комбинаторикой.   -  person Nixuz    schedule 10.04.2009

Ответы (2)


arrow_upward
15
arrow_downward

Возьмите произведение всех (частот + 1).

Например, в {A,B,B} ответ будет (1+1) [количество As] * (2+1) [количество Bs] = 6.

Во втором примере count(A) = 2 и count(B) = 2. Таким образом, ответ будет (2+1) * (2+1) = 9.

Причина, по которой это работает, заключается в том, что вы можете определить любое подмножество как вектор счетчиков — для {A,B,B} подмножества можно описать как {A=0,B=0}, {A=0,B=1 }, {0,2}, {1,0}, {1,1}, {1,2}.

Для каждого числа в counts[] есть (частоты этого объекта + 1) возможные значения. (0..частоты)

Следовательно, общее количество возможностей равно произведению всех (частот + 1).

Случай «все уникальные» также можно объяснить таким образом — каждый объект встречается только один раз, поэтому ответ будет (1+1)^|S| = 2^|S|.

person v3.    schedule 10.04.2009
comment
Как только я прочитал хотя бы первую часть вашего ответа, я понял, что он был прав. Теперь я чувствую себя глупо из-за того, что не видел этого, поскольку это довольно очевидно, когда кто-то это объясняет. В любом случае, спасибо, вы сэкономили мне много времени и нервов. - person Nixuz; 10.04.2009
comment
Но как он обрабатывает порядок чисел в подмножестве - person Nikhil Rathore; 25.01.2019
comment
Я не думаю, что это правильно. Для набора (a, b, a) количество подмножеств должно быть (2 + 1) * (1 + 1) = 6. Но включая пустое подмножество, есть 7 подмножеств. - person Nikhil Rathore; 25.01.2019
comment
@NikhilRathore, как ты получил 7-й? Имеет больше смысла, если вы представляете список как список подсчетов, как упомянул автор. Учитывая ваш пример (a, b, a) -> (a=2, b=1), может быть только 6: (a=0, b=0) [пустой набор], (a=0, b=1 ), (а=1, b=0), (а=1, b=1), (а=2, b=0), (а=2, b=1). - person Harry Cho; 18.03.2019

arrow_upward
4
arrow_downward

Я утверждаю, что эту проблему легко решить, если рассматривать ее должным образом. Вам не важен порядок элементов, важно только, появляются ли они в подмножестве или нет.

Подсчитайте, сколько раз каждый элемент появляется в наборе. Сколько существует подмножеств для набора из одного элемента {A}? Понятно, что комплектов всего два. Теперь предположим, что мы добавили еще один элемент B, отличный от A, чтобы сформировать множество {A,B}. Мы можем очень легко сформировать список всех наборов. Возьмите все наборы, которые мы сформировали, используя только A, и добавьте ноль или одну копию B. По сути, мы удваиваем количество наборов. Ясно, что мы можем использовать индукцию, чтобы показать, что для N различных элементов общее количество множеств равно 2^N.

Предположим, что некоторые элементы появляются несколько раз? Рассмотрим множество с тремя копиями A. Таким образом, {A,A,A}. Сколько подмножеств вы можете сформировать? Опять же, это просто. У нас может быть 0, 1, 2 или 3 копии A, поэтому общее количество подмножеств равно 4, поскольку порядок не имеет значения.

В общем, для N копий элемента A мы получим N+1 возможных подмножеств. Теперь расширим это, добавив некоторое количество M копий B. Итак, у нас есть N копий A и M копий B. Сколько всего подмножеств? Да, это тоже вроде понятно. К каждому возможному подмножеству, содержащему только A (их было N+1), мы можем добавить от 0 до M копий B.

Таким образом, общее количество подмножеств, когда у нас есть N копий A и M копий B, просто. Должно быть (N+1)*(M+1). Опять же, мы можем использовать индуктивный аргумент, чтобы показать, что общее количество подмножеств является произведением таких терминов. Просто подсчитайте общее количество повторов для каждого отдельного элемента, добавьте 1 и возьмите продукт.

Посмотрите, что происходит с набором {A,B,B}. Получаем 2*3=6.

Для набора {A,A,B,B} мы получаем 3*3 = 9.

person Community    schedule 10.04.2009