Nix*_*xuz 6 language-agnostic math set counting combinatorics
给定包含重复元素的集合**,如何确定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 | 给定一个"set"S(带有重复项),而不生成所有子集？
**技术上不是一套.
v3.*_*v3. 10
取所有(频率+ 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 |.