[人工智能]容斥原理

有n个集合，求这n集合的并集。

方法：容斥原理

公式：S₁ $?$ S₂ $?$ S₃ $?$ … $?$ S_n = $C_n^1$ - $C_n^2$ + $C_n^3$ - $C_n^4$ … (-1)^(n-1) $C_n^n$

共2ⁿ- 1项（ 二项式定理 ( 1 + 1 )ⁿ - $C_n^0$ 展开式 ）

例：有三个集合

S₁ = { 1, 2, 3, 4 }，S₂ = { 2, 3, 4, 5 }，S₃ = { 3, 4, 5, 6 }

$C_3^1$ ： S₁ , S₂ , S₃

$C_3^2$ ： S₁ $?$ S₂ = { 2, 3, 4 } ，S₁ $?$ S₃ = { 3, 4 } ， S₂ $?$ S₃ = { 3, 4, 5 }

$C_3^3$ ： S₁ $?$ S₂ $?$ S₃ = { 3，4 }

S₁ $?$ S₂ $?$ S₃ = S₁ + S₂ + S₃ - S₁ $?$ S₂ - S₂ $?$ S₃ - S₁ $?$ S₃ + S₁ $?$ S₂ $?$ S₃ = { 1, 2, 3, 4, 5, 6 }

实现方式

用代码实现集合方式可以利用二进制。

0表示不选，1表示选择，多少个集合二进制就多少位。

由上例：二进制011表示选择集合 S₁ S₂ 不选 S₃

$C_3^1$ ：001( S₁ ) ，010( S₂ ) ，100( S₃ )

$C_3^2$：011( S₁ $?$ S₂ ) ，101( S₁ $?$ S₃ ) ，110( S₂ $?$ S₃ )

$C_3^3$：111( S₁ $?$ S₂ $?$ S₃ )

可以观察到全部为1到111(2³- 1的二进制)中的项。

总结：所有组合情况均可由1到2ⁿ- 1的二进制数表示。

代码实现

// 从1枚举到1111（m个1）每个1位置对应着一个集合（最少一个集合）
for (int i = 1; i < 1 << m; i++)
{
	for (int j = 0; j < m; j++) // 枚举每一位
	{
		if (i >> j & 1) // 该位二进制对应的值
		{
			operation();  //对集合操作
		}
	}
}