最近在看 Greenplum 代码时发现一个比较有意思的代码片段, 这个代码片段解决了一个比较有意思的问题. 抽象着来说, 便是对于一个长度为 N 的数组 A, 数组 A 中每一个元素自身也是一个数组, 记集合 \(\{ M_1, M_2,..., M_N \}\) 为一个组合, 其中 \(M_i\) 为 A[i]
指向数组中成员之一. 现在需要设计一个过程可以完成对所有组合的遍历工作.
很显然, 对于 N 为编译期常数时这一过程非常简单. 比如 N = 3 时对应的遍历实现:
for (auto m1 : A[0]) {
for (auto m2 : A[1]) {
for (auto m3 : A[2]) {
/* 此时 {m1, m2, m3} 便是一个组合 */
}
}
}
但当 N 为变量时, 这一遍历过程的实现(最起码对我来说)还是挺让人头秃的. 老规矩, 先看下 N = 2 时能不能找到一个通用的遍历实现, 然后再以此类推. 为此我们先看一下一个比较直观的定理1:
对于长度为 2 的数组 A, A[0], A[1] 自身也指向着长度不同的数组. 记集合 \(Q1 = \{(a, b) | a \in [0, L0), b in [0, L1)\}\), \(Q2 = \{j | j \in [0, L0 * L1)\}\). 那么对于 Q1 中任意元素, 在 Q2 中都有且只有一个元素与之对应, 反之亦然.
这里 L0 即 A[0] 指向数组的长度, L1 即 A[1] 指向数组的长度. 该定理的证明也是比较直白的. 我们可以找到一个对应关系:
对于 Q2 中任意一个 j, 另
a = j % L0
,b = j / L0
, 即j = a + b * L0
显然此时 (a, b) 形成的集合与 Q1 相等, 定理得证. (emmm, 感觉少了很多东西…
也即对于 N = 2 时, 另一种遍历实现可以是:
for (int j = 0; j < L0 * L1; ++j) {
auto a = j % L0;
auto b = j / L0;
/* 此时 A[0][a], A[1][b] 便是一个组合 */
}
稍作一下结构上的调整, 得到遍历过程 F:
for (int j = 0; j < L0 * L1; ++j) {
std::vector<int> idxes;
for (int i = 0; i < length(A); ++i) {
idxes.push_back(j % length(A[i]));
j /= length(A[i]);
}
/* 此时 A[0][idxes[0]], A[1][idxes[1]] 便是一个组合 */
}
记得当 i = 1, 这里 \(j_1 \% L1\) 实际上便是 \((j_0 / L0) \% L1\), 考虑到 \(j_0\) 总是小于 L0 * L1
, 这里 \((j_0 / L0) \% L1\) 便是 \(j_0 / L0\) 了. 另外这里调整后得到的结构看上去是一个通用的结构, 如果我们能证明对于 N > 2 的情况, 如上结构也成立, 那么我们便解出了文章最开始提出的问题了.
所以我们这里考虑下 N = 3 的情况. 对于 A0, A1, A2, 我们暂且把 A0, A1 作为一个整体看待, 即认为他是一个长度为 L0 * L1 的数组 A01. 那么根据定理1可知, 对于 A01, A2 任意一个组合 (a01, a2)
, 这里 a01, a2 是组合中元素在各自数组中对应的下标, 都有 j = a01 + a2 * (L0 * L1)
与之对应, 并且此时 a01 = j % (L0 * L1)
. 再次应用定理1, 可得对于任一 a01 取值, 都对应着 A0, A1 的一个组合 (a0, a1)
, 此时 a01 = a0 + a1 * L0
, a0 = a01 % L0
, a1 = a01 / L0
. 即对于 A0, A1, A2 任一组合 (a0, a1, a2)
, 有且仅有一个 j = (a0 + a1 * L0 + a2 * (L1 * L2))
与之对应. 所以 N = 3 时对应的遍历过程可以写为:
for (int j = 0; j < L0 * L1 * L2; ++j) {
auto a0 = (j % (L0 * L1)) % L0;
auto a1 = (j % (L0 * L1)) / L0;
auto a2 = j / (L0 * L1);
/* 此时 A[0][a0], A[1][a1], A[2][a2] 便是一个组合 */
}
稍作推算便可得 (j % (L0 * L1)) % L0
等于 j % L0
. (j % (L0 * L1)) / L0
等于 (j / L0) % L1
, 这里我们简单写一下第二个推算过程(怕我再看时忘了==):
- 另
x = (j % (L0 * L1)) / L0
. 那么: j % (L0 * L1) = x * L0 + j % (L0 * L1) % L0
; 应用推算1可得:j % (L0 * L1) = x * L0 + j % L0
. 以及x < L1
(反证一下x >= L1
时等式肯定不会成立的便可得). 令k = j / (L0 * L1)
, 可得:j = k * (L0 * L1) + j % (L0 * L1)
, 即j = k * (L0 * L1) + x * L0 + j % L0
, 即:j = (k * L1 + x) * L0 + j % L0
, 也即:(k * L1 + x) = j / L0
. 再结合之前得到的x < L1
. 可得:x = (j / L0) % L1
.
所以, 上面的遍历过程便可变换为:
for (int j = 0; j < L0 * L1 * L2; ++j) {
auto a0 = j % L0;
auto a1 = (j / L0) % L1;
auto a2 = (j / (L0 * L1)) % L2;
/* 此时 A[0][a0], A[1][a1], A[2][a2] 便是一个组合 */
}
可以看到这里遍历过程是符合如上遍历过程 F 结构的, 即 F 可以用于 N = 3 的情况. 以此类推可知 F 适用于任何 N 的情况, 也即 F 便是文章开头提出问题的答案.