Как Вы вычисляете общее количество всех возможных уникальных подмножеств от набора с повторениями?
Создайте набор последних значений из списка, а затем посчитайте длину:
len(a) - len({x[-1] for x in a})
# 2
2 ответа
Возьмите произведение всех (частот + 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..frequencies)
Следовательно, общее количество возможных вариантов является произведением всех (частоты + 1).
Случай «все уникальности» также можно объяснить таким образом - каждый объект встречается по одному экземпляру, поэтому ответ будет (1 + 1) ^ | S | = 2 ^ | S |.
Я буду утверждать, что эту проблему легко решить, если ее правильно рассмотреть. Вам не важен порядок элементов, только если они появляются в подмножестве not.
Подсчитайте, сколько раз каждый элемент появляется в наборе. Для одного набора элементов {A} сколько существует подмножеств? Очевидно, есть только два набора. Теперь предположим, что мы добавили еще один элемент, отличный от 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.