生成排列和子集

这个只是单纯的总结，之后肯定还会搞的（如果没有退役的话）。

生成排列

不妨以生成 $1 \sim n$ 的排列进行举例子，我们对于每一个数字的上面先定一个箭头，表示其可以向那边走。

一个数字移动的条件是其箭头指向的相邻的数组比其要小。

例如 $\overset{\leftarrow}{1}\overset{\leftarrow}{2}$ 这个时候 $2$ 就是可以向左走一个位置的，也就是意味着下一个排列是 $\overset{\leftarrow}{2}\overset{\leftarrow}{1}$。

我们构造一个排列是从 $\overset{\leftarrow}{1}\overset{\leftarrow}{2} \dots \overset{\leftarrow}{n}$ 开始的。

  • 每次找到最大的可以移动的数。
  • 交换其和其箭头指向的数字。
  • 交换所有 $i, i > m$ 的箭头的方向。

逆序对生成排列

对于一个数组 $b$，$b_i$ 表示第 $i$ 个位置的逆序对数量。

我们从左到右进行考虑。

首先写出 $n$，先钦定其为第一个数字。

之后对于下一位如果 $b_2 = 0$ 那么就是放在 $n$ 的左边，不然是右边。

对于第 $k$ 位来说其放置的位置就是原来数列的第 $b_k$ 个位置。

显然这种构造是一个唯一对应一个排列的。

Gray Code

我们发现直接使用二进制进行传输信息使用的空间大小是不确定的，比如说传输 $7 = (111)_2$ 和传输 $8 = (1000)_2$。

格雷码就是构造一种使得相邻数字的二进制编号 $1$ 的个数只相差 $1$ 的编码。而且其只会使用小于最大编号的二进制位，这样的编码就是唯一的。

如何构造?

对于第 $n$ 位可以直接由公式得到 g(n) = n ^ (n >> 1)。

或者我们考虑从小到大进行构造，也就是对于 $2^{n - 1}$ 的格雷码，我们现在前面全部放 $0$ 之后再在前面放 $1$ 两段一起拼起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
1

00
01
10
11

000
001
010
011
100
101
110
111
如何翻转格雷码？
1
2
3
4
5
int rev_g(int g) {
    int res(0);
    for(; g; g >>= 1) res ^= g;
    return res;
}

后面的生成子集就先鸽一下。