给定一个包含重复元素的集合S，如何确定S的所有可能子集的总数，其中每个子集都是唯一的。例如，假设S = {A，B，B}并且设K是所有子集的集合，则K = {{}，{A}，{B}，{A，B}，{B ，B}，{A，B，B}}，因此| K |另一个例子是如果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（带有重复项），而不生成所有的子集？
**不是技术上的一套。
取所有（频率+ 1）的乘积。
例如，在{A，B，B}，答案是（1 + 1）[在作为数] *（2 + 1）[B的数量] = 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 |。
我会说这个问题很容易解决，当以正确的方式查看时。你不关心元素的顺序，只关心它们是否出现在非子集的子集中。
计算每个元素出现在集合中的次数。对于一个元素集合{A}，那里有多少个子集？显然只有两套。现在假设我们添加了不同于A的另一个元素B，以形成集合{A，B}。我们可以很容易地形成所有组的列表。将所有我们仅使用A形成的集合，并添加零或一个B副本。实际上，我们将集合的数量加倍。显然，我们可以用归纳法来表明，对于N个不同的元素，总集合数仅为2^N。
假设某些元素多次出现？考虑具有三个A副本的集合。因此{A，A，A}。你可以形成多少个子集？再一次，这很简单。我们可以有0,1,2或3个A副本，所以子集的总数是4，因为顺序无关紧要。通常，对于元素A的N个副本，我们将以N + 1个可能的子集结束。现在，通过添加一些M的副本来扩大这个范围。因此，我们有B个A和M个副本的副本N个。那里有多少个子集？是的，这似乎也很明显。对于只有A的每个可能的子集（有N + 1个），我们可以在B和0之间添加M个副本。
因此，当我们有N份A和M份B副本时，子集的总数很简单。它必须是（N + 1）*（M + 1）。再次，我们可以使用归纳论证来表明子集的总数是这些术语的乘积。仅计算每个不同元素的总重复次数，加1，然后取出产品。
看看集合{A，B，B}会发生什么。我们得到2 * 3 = 6
对于集合{A，A，B，B}，我们得到了3 * 3 = 9
这的确是一个数学问题，而不是一个编程的问题。 – Eddie 2009-04-10 02:04:01
这是一个编程相关的问题，我有这样的公式对于分析某些组合相关算法的运行时间很重要。 – Nixuz 2009-04-10 02:28:33