language-agnostic - 如何计算具有重复的集合中所有可能的唯一子集的总数？

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}。

对于counts []中的每个数字，都有(该对象的频率+ 1)可能的值。 (0 ..频率)

因此，可能性的总数是所有(频率+1)的乘积。

“所有唯一”情况也可以用这种方式解释-每个对象都出现一次，因此答案为(1 + 1)^ | S |。 = 2 ^ | S |。