各种遍历算法

Published: July 18, 2021 by Daltao

Categories:
algorithm 101

通过叶子统计树上结点数
置换遍历
k大子集遍历

通过叶子统计树上结点数

对于一颗有根树，如果所有非叶子结点都至少有两个孩子（等价的不存在度数为 $2$ 的结点），那么我们就可以用叶子数来约束整个树的大小，这样的树我们称其为无杆树。记 $n$ 表示叶子数， $m$ 表示非叶子数，实际上可以发现 $m\leq n$ ，因此总的树上结点数不超过 $2n$ 。

证明非常简单，我们可以不断选择最深的一个叶子，将其父亲下的所有叶子全部删除。可以发现这样一次操作，至少会减少两个叶子，并出现一个新的叶子，因此总的叶子数至少减少了 $1$ ，且重要的是操作后得到的新树依旧是无杆树。可以发现不断执行上面操作，直到只剩下一个根结点，我们总共最多执行 $n$ 次操作，但是将 $m$ 个非叶结点都转换成了叶子结点，因此有 $m\leq n$ 成立。但是如果我们将根也视作一个叶子的话，可以发现有 $m<n$ 成立。

上面这个技术在证明树形递归（无环）算法时间复杂度的时候非常有用。考虑一个经典的递归枚举子集算法：

void gen(int[] bits, int i, int sum){
    if(i == -1){
        //组合已经生成完毕，做一些操作
        return;
    }
    gen(bits, i - 1, sum);
    bits[i] = 1;
    gen(bits, i - 1, sum + 1);
    bits[i] = 0;
}

将每次调用视作树上的一个结点，我们发现时间复杂度恰好是 $O(n+m)$ 。这里可以发现形成的树是无杆树，而叶子总数仅有 $O(2^s)$ 个，其中 $s$ 是全集的大小。因此总的时间复杂度为 $O(2^s)$ 。由于递归遍历的时候可以维护选中的子集的摘要信息，因此实际上比一般暴力循环的 $O(s2^s)$ 的时间复杂度会好上很多。

再考虑一个经典的递归枚举置换算法：

void gen(int[] perm, int i, boolean[] used) {
    if(i == -1){
        //排列已经生成，做些操作
        return;
    }
    for(int j = 0; j < used.length; j++){
        if(used[j]){
            continue;
        }
        used[j] = true;
        perm[i] = j;
        gen(perm, i - 1, used);
        used[j] = false; 
    }
}

设 $p$ 为置换的长度。依旧我们将每次调用视作树上的一个结点，可以发现深度为 $p$ 和 $p-1$ 的调用次数都是 $p!$ ，而深度小于等于 $p-1$ 的部分是形成了一颗无杆树。因此树上结点总数为 $O(p!)$ 。而每个结点（每次函数调用）消耗的时间复杂度为 $O(p)$ ，因此总的时间复杂度为 $O((p+1)!)$ 。

置换遍历

要遍历所有大小为 $n$ 的置换，我们一般有递归和迭代两种方式。

递归方式可以用于处理全排列，时间复杂度为 $O(n\cdot n!)$ 。好处是可以计算的时候附带处理一些约束条件，以及计算一些汇总信息。递归方式适用于生成大量的排列的情况，而它计算单个排列（比如计算某个排列的后继）的最坏时间复杂度为 $O(n^2)$ 。这时候我们可以使用迭代的方式来优化。

迭代算法分成两类，计算某个置换的后继和前驱。我们先考虑后继，前驱版本可以逆向思维得到。

对于 $P$ ，如何找到比 $P$ 大且在这些置换中最小的置换呢 $T$ 。我们应该保证 $P$ 和 $T$ 的公共前缀尽量长。因此我们要选择一个最短的后缀，通过调整后缀得到一个更大的置换。

很显然后缀是倒序的时候，我们不可能通过调整它得到更大的一个置换，考虑 $i$ 为最大的下标，且满足 $P_i<P_{i+1}$ 。我们先对 $P_{i+1},\ldots,P_n$ 进行排序（考虑到它们是倒序的，因此只要翻转即可）。之后我们将 $P_i$ 和排序完的 $P_{i+1},\ldots,P_n$ 中最小的但是比 $P_i$ 大的数交换，就可以得到后继了。

注意迭代算法是支持排列中出现相同的元素的。它计算单个排列的最坏时间复杂度为 $O(n)$ 。但是当保证置换中不存在相同的值的情况下，我们可以得出更加好的平均时间复杂度，下面我们进行计算。

很显然单次操作的时间复杂度取决于具体翻转了多少个元素。可以发现如果我们当前操作翻转了最后 $t$ 个元素，那么下一次翻转 $t$ 或更多元素，必须在 $t!$ 轮之后。即如果我们要找的是第 $k$ 大的排列，那么这一轮中会翻转的元素等价于找到最大的一个 $i$ ，满足 $i!\mid k$ ，这一轮会翻转 $i$ 个元素，记 $i=f(k)$ 。

现在考虑 $k$ 是均匀随机给定的，那么 $\mathrm{Pr}(f(k)=i)=\frac{1}{i!}-\frac{1}{(i+1)!}=\frac{i}{(i+1)!}$ 。那么单次翻转的期望费用可以写作 $E[\sum_{i=1}^n (i+1)x_i]$ ，其中 $x_i$ 表示当前轮是否翻转 $i$ 个元素。答案为 $\sum_{i=1}^n (i+1)\mathrm{Pr}(f(k)=i)=\sum_{i=0}^{n-1}\frac{1}{i!}\leq e$ 。因此我们可以认为一次操作的平均时间复杂度为 $O(e)$ 。

迭代算法中前驱和后继的计算逻辑相似，都是翻转尾部，以及一次交换操作。所以可以得出相同的时间复杂度，这里不赘述。

k大子集遍历

所谓的k大子集是正好包含k个元素的子集。

k大子集遍历的算法有不少。最简单的方式就是使用一个包含k个1的置换，并使用置换遍历算法来枚举所有的，但是时间复杂度不太清楚。

还有一个叫做Gosper's Hack的算法。它的代码如下：

// find next k-combination
bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary
{
  unsigned long u = x & -x; // extract rightmost bit 1; u =  0'00^a10^b
  unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b
  if (v==0) // then overflow in v, or x==0
    return false; // signal that next k-combination cannot be represented
  x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a
  return true; // successful completion
}

上面的代码来自wiki。

很显然它是 $O(1)$ 的，原理我也没去了解。

但是这个算法只能处理形如 $S=2^n-1$ 这样的集合的子集。之前没有注意，一直以为可以处理任意形式的子集，结果某次Topcoder比赛上用了这个板子，最终成功FST了。

下面讲一下具体如果找任意集合的所有k大子集。原本是希望通过改造Gosper's Hack算法来实现，但是里面用到下整除的黑魔法，搞不太定。下面讲一下我的做法。

我们先考虑 $S=2^n-1$ 的形式，我们要从小到大枚举 $S$ 的所有的k大子集。我们维护最低位1所在连通块的信息（如果两个1相邻，我们认为它们在一个连通块中），假设它们的范围从第l位开始，到第r位结束。

现在我们考虑要找到下一个k大子集。怎么找，根据取下一个置换的算法，实际上我们需要将第 $r+1$ 位设置为 $1$ ，将 $l$ 到 $r$ 位设置为 $0$ ，之后将 $0$ 到 $r-1-l$ 位都设置为 $1$ 。

由于只涉及一些二进制操作，实际上我们可以 $O(1)$ 执行上面所有的操作。难点在于要维护 $l$ 和 $r$ 。如果 $r-1\geq l$ ，那么上面的流程后我们能很容易维护新的 $l',r'$ 。否则，新的 $l'=r+1$ ， $r'$ 的话我们可以暴力从 $l'$ 开始查找，直到找到第一个 $0$ 位置。

上面涉及到暴力查找 $r'$ 的过程是摊还 $O(1)$ 的，可以认为我们每次我们右移一个 $1$ 的时候（对应将 $r$ 位置 $0$ ,将 $r+1$ 位置 $1$ ），我们实际支付了两笔费用，一笔是移动的费用，一笔是支付后面用于扫描的费用。很显然一个被扫描的 $1$ 之前一定被移动过，因此扫描的时候可以用预付的费用来支付。摊还时间复杂度为 $O(1)$ 。

因此总的每次调用的时间复杂度均为 $O(1)$ 。

现在你可能会问，这个算法和Gosper's Hack解决的问题有什么不同吗？

解决的问题是一样的，但是这个新的算法很容易扩展。现在考虑任意的集合 $S$ ，我们先将其中所有 $1$ 出现的位置进行排序，记第 $i$ 个 $1$ 出现的位置为 $p_i$ ，并假设其中出现了 $n$ 个 $1$ 。之后我们维护另外一个集合 $T=2^n-1$ 。之后我们用上面提到的算法遍历 $T$ 的所有k大子集 $t$ ，同时我们为 $S$ 维护对应的k大子集 $s$ 。这样对所有 $t$ 的操作，我们可以同步修改 $s$ ，比如设置 $t$ 的第 $i$ 位，等价于设置 $s$ 的 $p_i$ 位，而反转 $t$ 的 $l,r$ 区间，等价于我们让 $s$ 先异或上 $2^{p_1}+\ldots+2^{p_r}$ ，之后再异或上 $2^{p_1}+\ldots+2^{p_{l-1}}$ ，这部分可以通过前缀和计算。

因此我们得到了一个预处理 $O(\log_2 S)$ ，且 $O(1)$ 计算下一个k大集合的算法。

实际上这个算法非常容易扩展，考虑我们需要同时计算得到的k大集合的一个摘要（比如给集合每个元素赋予一个权重，要算子集的权重和）。一般的做法会每次计算下一个k大集合的时候时间复杂度提高到 $O(k)$ ，但是实际上我们可以同步维护当前的摘要信息，只要它支持批量增加元素和批量删除元素。这样时间复杂度依旧不变，是 $O(1)$ 。