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

Question

Учитывая набор ** 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 (с дубликатами), без генерации всех подмножеств?

** Технически не установлен.

Answer 1

Возьмите продукт всех (частоты + 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}.

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

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

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

Answer 2

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

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

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

В общем случае для N копий элемента A мы получим N + 1 возможных подмножеств. Теперь расширьте это, добавив в некоторое число М экземпляров 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.