给定重复元素集中不同元素子集总数的算法

Question

我必须找出“k”的子集总数 (k > 1)，长度包含不同的元素。如果碰巧有相同的元素但具有不同的索引，则两个子集被认为是不同的。请参见下面的示例。

Given a Set A={1, 1, 2, 3}.

For k=2, the possible subsets are {1(index=1), 2}, {1(index=2), 2}, {1(index=1), 3}, {1(index=2), 3} and {2, 3}. Total=5.

For k=3,the possible subsets are {1(index=1), 2, 3}, {1(index=2), 2, 3}. Total=2.

For k=4,possible subsets=0.

我必须为长度为 10^5 的数组计算这个。有什么组合逻辑吗？

Answer 1

这是一个O(m * k) 方法，其中m 是A 中不同元素的数量。

将 A 中的每个不同元素映射到它的出现次数(您可以为 O(n) 运行时使用 HashMap )。让这些数字成为

c[1], c[2], ..., c[m]

现在您可以看到 k 个不同的集合的总数是所有可能乘积的总和

c[i1] * c[i2] * ... * c[ik]

(在您的示例中，c[1] = 2, c[2] = 1, c[3] = 1 并且您可以看到具有 2 个不同元素的集合的数量是 2*1+1*1+2*​​1 = 5)。

你还可以看到这个数是多项式中x^k前面的系数:

(1+c[1]*x)*(1+c[2]*x)*...*(1+c[m]*x)

这可以通过用每个多项式 1 + c[i]* x.

运行时间是O(m * k)。