计算四元组整数的个数

Question

I saw this question today where we need to count the number of quadruples of integers (X1, X2, X3, X4), such that Li ≤ Xi ≤ Ri for i = 1, 2, 3, 4 and X1 ≠ X2, X2 ≠ X3, X3 ≠ X4, X4 ≠ X1.

我最初的想法是使用

Principle of Inclusion Exclusion

我能够找到 number if unrestricted quadruples 但我无法弄清楚我们如何才能找到剩余的条件来达到最终解决方案。我也开始知道这个问题可以使用 DFS 来完成。

我们如何使用 Inclusion Exclusion/ DFS 做这道题

Answer 1

Inclusion/Exclusion 会给你四胞胎的数量，但不会给你四胞胎本身。

设Ai是满足所有j的Lj<=Xj<=Rj的四元组集合，其中Xi=X(i+1)（其中索引是循环的，所以X5表示X1）。在您提供的示例中，

A1 = { (1114), (1124), (2214), (2224), (3314), (3324) }
A2 = { (1114), (2114), (3114), (4114), (1224), (2224), (3224), (4224) }
A3 = { } (empty set)
A4 = { (4114), (4214), (4314), (4124), (4224), (4324) }

我们还需要集合对的交集：

A1 cap A2 = { (1114), (2224) } (note first three numbers identical)
A1 cap A3 = { }
A1 cap A4 = { } (can't have X4=X1=X2)
A2 cap A3 = { }
A2 cap A4 = { (4114), (4224) }
A3 cap A4 = { }

三元组的交集：

A1 cap A2 cap A3 = { }
A1 cap A2 cap A4 = { }
A1 cap A3 cap A4 = { }
A2 cap A3 cap A4 = { }

所有集合的交集：

A1 cap A2 cap A3 cap A4 = { }

Inclusion/exclusion 的互补形式告诉我们

|intersection of complements of Ai| = |unrestricted quadruples| 
- sum of |Ai| + sum of |Ai cap Aj| - sum of |Ai cap Aj cap Ak| 
+ sum of |Ai cap Aj cap Ak cap Al|

其中索引 i、j、k、l 的 none 相等。在你的例子中，

|intersection of complements of Ai| = 4x3x2x1 - (6+8+0+6) + (2+0+0+0+2+0) - (0+0+0+0) + 0 
= 24 - 20 + 4 - 0 + 0 = 8

为了找到|Ai|及其交点，您必须找到区间 [Li,Ri] 的交点，并将交点的长度乘以不受限制的区间的长度。例如，

|A1| = |[1234] cap [123]| x |[12]| x |[4]| = 3 x 2 x 1 = 6
|A2 cap A4| = |[123] cap [12]| x |[4] cap [1234]| = |[12]| x |[4]| = 2 x 1 = 2

在这种方法中，我看不出深度优先搜索与它有什么关系。

Answer 2

这取决于集合是不相交的还是共享元素。对于 n = 4，意思是四元组，正如你所问的，如果我们将末端提交给描述 x_1 是否是 X2 的成员的四种类型，我想我将它减少到 1 到 4 次迭代之间x_4 X3.

的成员

具有三个迭代的示例：

input = {1,2,3}{1,2}{1,2,3}{3,4}

2 * (1)(12)(123)(3) = (1)(2)(1)(3) = 2 * 1          // x_1 ∈ X2, x_4 ∈ X3
2 * (1)(12)(123)(4) = (1)(2)(13)(4) = 2 * 2          // x_1 ∈ X2, x_4 ∉ X3
1 * (3)(12)(123)(4) = (3)(12)(12,3)(4) = 1 * (2 + 2)  // x_1 ∉ X2, x_4 ∉ X3
Total = 10

一次迭代示例：

input = {1,2,3,4}{1,2,3,4}{1,2,3,4}{1,2,3,4}          // x_1 ∈ X2, x_4 ∈ X3

12 * (1)(1234)(1234)(2) = (1)(2,34)(134)(2) = 12 * (3 + 4)
Total = 84

计算四元组整数的个数

Counting number of quadruples of integers

algorithm

depth-first-search