最少的检查来查找列表中的重复项

给定一个序列 (d1, d2, ..., dn)，我想计算所有 i != j 的乘积 (1 - Dij)，其中如果 di = dj，则 Dij = 1，否则为 0。

我的代码仅在我时检查 Dij

prod = 1;
for (int i=1; i<n; ++i) {
    for (int j=i; j<=n; ++j) {
        prod *= (1 - Dij);
    }
}

我知道当我得到 Dij=1 时我可以停下来，但我想做的是获取要检查的 Dij 的最小表达式。这样我就有了一个表达式，然后我可以使用差异序列并对其进行评估。所以我知道我能做到i<j代替i != j。所以我想扩展这个产品并得到 n=3 的类似结果：

(1 - D12) (1 - D13) (1 - D23) = 1 - D12 - D13 - D23 + D12*D13 + D12*D23 + D13*D23 - D12*D13*D23

但我能做的还有更多。这个表达式实际上总是等于

1 - D12 - D13 - D23 + 3 * D12*D13 - D12*D13*D23

我的问题是：

1. 为什么D12 * D13 = D12 * D23？这总是正确的（意味着 d 序列是什么并不重要），但我真的不明白为什么，因为在我看来，这意味着 D13 = D23 这并不总是正确的（它取决于 d 序列） 。这种关系有助于使表达式更小。

2. 我怎样才能找到所有这样的关系并得到一个最小表达式？上面的表达式是最小的吗？我什至不知道。

您正在尝试确定 D 是否包含任何重复项。最终，这需要您将每个条目相互比较，这只是枚举两个元​​素的所有唯一组合。最终结果是N*(N-1)/2。您可以通过先对 D 进行排序，然后搜索重复的相邻对（O(N*log(N)），或者，假设您坚持整数的有限范围，您可以使用位向量将其减少到线性时间，或者如果您喜欢冒险，则可以使用基数排序。