在列表中查找重复项的最小检查

Question

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

The code I have only checks Dij when i

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

I know I can stop when I get Dij=1, but what I'm trying to do is get a minimal expression of the Dij's to check. This way I have one expression and then I can use difference sequences and evaluate it. So I know that I can do i<j instead of i != j. So I want to expand out this product and get something like this for n=3:

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

But there is more that I can do. This expression is actually always equal to

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

My questions are:

1. Why is D12 * D13 = D12 * D23? This is always true (meaning it doesn't matter what the d sequence is) but I don't really get why because it seems to me that this means D13 = D23 which isn't always true (it depends on the d sequence). This is the relation that helps make the expression smaller.

2. How can I find all the relations like this and get a minimal expression? Is the expression above minimal? I don't even know.

- Daniel

---

这可能更适合于http://math.stackexchange.com。 - PengOne

DXY类似于真值表。对于D12 * D13 == 1，你需要d1==d2和d1==d3，此时，显然d2==d3（即D23=1）。 - Dr. belisarius

为什么你要基于Dij-s计算乘积，而不是基于di-s呢？ - Karoly Horvath

因为我想要一个通用的表达式，以后可以用于许多不同的序列。 - Daniel

是的，这可以工作！但是对于更大的命名空间，我该如何找到它呢？ - Daniel

Answer 1

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

- MSN

Answer 2

我可以为您翻译成中文：

我能为您解答第一个问题。考虑下面两种情况：

情况1：D13 = D23

在这种情况下，您只需在两边同时乘以D12即可得到D12 * D13 = D12 * D23。

情况2：D13 != D23

这意味着要么d1 = d3 XOR d2 = d3但不是两者同时满足。因此我们知道d1 != d2。这意味着D12 = 0。因此，

D12 * D13 = 0 * D13 = 0 = 0 * D23 = D12 * D23

你认为这意味着 D13 = D23 的逻辑问题在于你不能除以 0，而且 D12 可能是 0（就像在第二种情况下总是发生的那样）。

---

您的第二个问题很有趣，我并不是立刻就知道答案，但是这里有一些观察结果可能会有所帮助。

请将数字1、2、...、n按顺序排列在一行上：

1  2  3 ... n

给定一个表达式 D_(i1,j1) * D_(i2,j2) * ... * D_(ik,jk)，从 i1 到 j1，i2 到 j2 等等制作一条弧。这将该行转换为图形（顶点是数字，边缘是这些弧）。

该图的每个连通组件表示数字集合 1, 2, ..., n 的子集，并且作为整体给出了 {1, 2, ..., n} 的 set partition。 事实：具有相同对应集合划分的任何两个项都是相等的。

例如：

D12 * D23 = D12 * D13

               ---------
              |         |
1 -- 2 -- 3 = 1 -- 2    3

有时候这个事实意味着学位是相同的，就像上面的情况一样；而有时候学位会降低，就像下面这个例子。

D12 * D13 * D23

 ---------
|         |
1 -- 2 -- 3

结果是现在你可以将产品（1-Dij）表示为集合划分的总和：

\prod_{i<j} ( 1 - Dij ) = \sum_{P set partition of \{1,2,...,n\}} c_P * m_P

其中单项式项由以下表示：

mP = mP1 * mP2 * ... * mPk

当 P = P1 ∪ P2 ∪ ... ∪ Pk，且如果 Pi = { a < b < c < ... < z }，则

m_Pi = Dab * Dac * ... * Daz

最后，系数项只是

c_P = \prod (#P1)! (#P2)! ... (#Pn)!

经过思考，我现在确定这个问题应该放在http://math.stackexchange.com而不是这里。

- PengOne

---

好的。你能告诉我如何使用容斥原理来找到最小表达式吗？我不是很清楚那是什么。 - Daniel

Answer 3

我没有跟进这个数学问题，但是这不是可以使用哈希表编码的东西吗？或者如果你知道di的大小受限，甚至可以使用稀疏位数组。只需遍历列表，在与di值对应的位置上用“1”填充数据结构 - 如果已经是1，则返回0。如果完成（在n步骤中），则返回1。它应该是O（n）。

- Mike Sokolov