如何 O(1) 排序
cancan123456
·
·
个人记录
我们现做如下假设：
-
输入有 n 个数，以一个二进制数构成，比如二进制数 11,1011,1110,1 压缩为二进制数 00011\text{ }01011\text{ }01110\text{ }00001（请记住每个数字前面的 0，以后要考）。
-
输出以同样的方式压缩。
-
整数串中每个数的位数都必须相等，位数不够用零补足。这个位数称为定宽或 w，本文的例子的 w 为 4。
-
对于任意大小的整数，其赋值、四则运算、取余运算、比较运算、位运算都能够在 O(1) 的时间内完成。
-
没有重复。
那么我们开始。
考虑如下排序算法：
给定 n 个数 a_1,a_2,a_3,\dots,a_n，对于每个数，枚举有几个数小于其，设有 x_i 个数小于 a_i，那么将 a_i 存入 b_{x_i}，那么 b_i 就是 a_i 排序的结果。
首先，假设我们要对 0100\text{ }0111\text{ }0001\text{ }0010 排序，我们考虑把原来的串扩展成 A,B 两个串：
A=0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010
B=0100\text{ }0100\text{ }0100\text{ }0100\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0010\text{ }0010\text{ }0010\text{ }0010
而我们有：
$$mask=\frac{1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111\text{ }1111}{1111\text{ }1111\text{ }1111\text{ }1111}=\frac{2^{64}-1}{2^{16}-1}$$
写成通用的形式，就是：
$$mask=\frac{2^{n^2w}-1}{2^{nw}-1}$$
这样我们在后面就可以一起比较 $O(n^2)$ 个数对了。
我们将 $B$ 看做：
$$B=0000\text{ }0000\text{ }0000\text{ }0100\text{ }0000\text{ }0000\text{ }0000\text{ }0111\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0010\times0001\text{ }0001\text{ }0001\text{ }0001$$
那么前面这个操作等价于加大 $w$，这个操作不好做，但我们发现，如果我们把 $A=0000\text{ }0000\text{ }0000\text{ }0000\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010$ 和 $0000\text{ }0000\text{ }0000\text{ }0000\text{ }1111\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }1111\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }1111\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }1111$ 按位与一下，就可以得到：
$$0000\text{ }0000\text{ }0000\text{ }0000\text{ }0100\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0111\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0010$$
这就很接近 $B$ 了，我们现在要缩小 $w$。
如果 $w'\times n\le w$，我们就可以将一个定宽 $w$ 的串缩减为定宽为 $w'$ 的序列，具体来说，将
$$0000\text{ }0000\text{ }0000\text{ }0000\text{ }0100\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0111\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0010$$
对 $1111\text{ }1111\text{ }1111\text{ }1111$ 取模，就可以得到原来的 $0100\text{ }0111\text{ }0001\text{ }0010$（其实这个操作相当于把原来的数截成 $16$ 位的然后再相加）。
然后我们通过两次操作把定宽扩大到 $(n+1)^2w$，然后再缩到 $n\cdot w$，再乘 $0001\text{ }0001\text{ }0001\text{ }0001$，我们就得到了 $B$。
然后我们拿到了 $A$ 和 $B$。
我们考虑计算 $a-b$，在计算机里是 $a+(\sim b)$，其中 $\sim$ 表示按位取反，如果最高位符号位是 $1$ 那么说明是负数，也就是 $a<b$，否则 $a>b$。
所以我们取的 $w$ 应该是最大位数加 $1$。
那么我们就可以按照如下步骤操作：
$$0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }0100\text{ }0111\text{ }0001\text{ }0010$$
A 串。
$$0100\text{ }0100\text{ }0100\text{ }0100\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0010\text{ }0010\text{ }0010\text{ }0010$$
B 串。
$$1011\text{ }1011\text{ }1011\text{ }1011\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1110\text{ }1110\text{ }1110\text{ }1110\text{ }1101\text{ }1101\text{ }1101\text{ }1101$$
对 $B$ 取反。
$$0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }0111\text{ }$$
一个掩码。
$$0011\text{ }0011\text{ }0011\text{ }0011\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0110\text{ }0110\text{ }0110\text{ }0110\text{ }0101\text{ }0101\text{ }0101\text{ }0101$$
将 $B$ 中符号位置 $0$。
$$0111\text{ }1010\text{ }0100\text{ }0101\text{ }0100\text{ }0111\text{ }0001\text{ }0010\text{ }1010\text{ }1101\text{ }0111\text{ }1000\text{ }1001\text{ }1100\text{ }0110\text{ }0111$$
$A$ 和上面一个序列相加。
$$1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000\text{ }1000$$
另外一个掩码。
$$0000\text{ }1000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }1000\text{ }1000\text{ }0000\text{ }1000\text{ }1000\text{ }1000\text{ }0000\text{ }0000$$
两者按位与。
$$0000\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0001\text{ }0000\text{ }0001\text{ }0001\text{ }0001\text{ }0000\text{ }0000$$
右移 $w-1$ 位。
最后这个结果中，$1$ 表示 $B$ 对应位置比 $A$ 大，否则就是 $A$ 对应位置比 $B$ 大。
如果原来的数字串没有重复，那么这个里面应该有 $\dfrac{n(n-1)}2$ 个 $1$。
把结果对 $1111\text{ }1111\text{ }1111\text{ }1111$ 取模，得到：
$$0010\text{ }0011\text{ }0000\text{ }0001$$
这里面第一个数 $0010$ 表示原串中有 $2$ 个数比第一个数 $0100$ 小，我们将这个序列称为 $index$。
我们先构造这个序列：
$$count=0000\text{ }0001\text{ }0010\text{ }0011$$
也就是：
$$\sum_{i=0}^{n-1}i2^{w(n-i-1)}$$
我们直接 Mathematica 算一下：
$$\sum_{i=0}^{n-1}i2^{w(n-i-1)}=\frac{2^{nw}+n-2^wn-1}{(2^w-1)^2}$$
然后我们把 $index$ 与 $count$ 比较一下，套用上面的所有步骤：
$$0010\text{ }0010\text{ }0010\text{ }0010\text{ }0011\text{ }0011\text{ }0011\text{ }0011\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0001\text{ }0001\text{ }0001$$
（扩展的 $index$ 序列）
$$0000\text{ }0001\text{ }0010\text{ }0011\text{ }0000\text{ }0001\text{ }0010\text{ }0011\text{ }0000\text{ }0001\text{ }0010\text{ }0011\text{ }0000\text{ }0001\text{ }0010\text{ }0011$$
（扩展的 $count$ 序列）
$$0001\text{ }0000\text{ }0000\text{ }0001\text{ }0001\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000$$
（对应位置上 $index$ 小）
$$0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0001\text{ }0001\text{ }0000\text{ }0001\text{ }0001$$
（对应位置上 $count$ 小）
我们用 $\text{or}$ 和 $\text{xor}$ 提取出两个串都是 $0$ 的位置：
$$0001\text{ }0001\text{ }0000\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0000\text{ }0000\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0000\text{ }0001\text{ }0001$$
两个序列按位或。
$$0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001\text{ }0001$$
一个掩码。
$$0000\text{ }0000\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0001\text{ }0000\text{ }0000$$
两者异或。
$$0000\text{ }0000\text{ }1111\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }1111\text{ }1111\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }1111\text{ }0000\text{ }0000$$
乘 $2^w-1$。
然后与 $B$ 按位与：
$$0000\text{ }0000\text{ }0100\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0111\text{ }0001\text{ }0000\text{ }0000\text{ }0000\text{ }0000\text{ }0010\text{ }0000\text{ }0000$$
最后的数满足出现的数与原串相同，且每个数都在排序后的位置上，所以我们对 $1111\text{ }1111\text{ }1111\text{ }1111$ 取模，就可以得到最终的结果：
$$0001\text{ }0010\text{ }0100\text{ }0111$$
好，前面说了这么多，我们放一下代码。
```python
def print_in_binary(num, n, w):
res = bin(num)[2:]
res = '0' * (n * w - len(res)) + res
ans = ''
for i in range(n):
ans += res[i * w : i * w + w] + ' '
print(ans)
def get_1(n):
return (1 << n) - 1
def get_mask(n, w):
return get_1(n * w) // get_1(w)
def get_count(n, w):
return ((1 << n * w) + n - (n << w) - 1) // (((1 << w) - 1) ** 2)
def get_A(a, n, w):
return a * get_mask(n, n * w)
def inc_w(a, n, w):
return get_A(a, n, w) & (get_mask(n, (n + 1) * w) * get_1(w))
def get_B(a, n, w):
B = inc_w(a, n, w)
B = inc_w(B, n, w * (n + 1))
B = B % get_1(w * (n + 1) * (n + 1) - w * n)
B = B * get_mask(n, w)
return B
def sort_in_binary(a, n, w):
A = get_A(a, n, w)
B = get_B(a, n, w)
notB = get_1(n * n * w) ^ B
notB = notB & (get_mask(n * n, w) * get_1(w - 1))
index = ((notB + A) & (get_mask(n * n, w) << (w - 1))) >> (w - 1)
index = index % get_1(n * w)
count = get_count(n, w)
indexB = get_B(index, n, w)
countA = get_A(count, n, w)
notindexB = get_1(n * n * w) ^ indexB
notindexB = notindexB & (get_mask(n * n, w) * get_1(w - 1))
index_small = ((notindexB + countA) & (get_mask(n * n, w) << (w - 1))) >> (w - 1)
notcountA = get_1(n * n * w) ^ countA
notcountA = notcountA & (get_mask(n * n, w) * get_1(w - 1))
count_small = ((notcountA + indexB) & (get_mask(n * n, w) << (w - 1))) >> (w - 1)
result = index_small | count_small
result = result ^ get_mask(n * n, w)
result = result * get_1(w)
result = result & B
answer = result % get_1(w * n)
return answer
# test [00011, 01011, 01110, 00001]
#n = 4
#w = 5
#a = int("00011010110111000001", 2)
# test [0100, 0111, 0001, 0010]
n = 4
w = 4
a = int("0100011100010010", 2)
print_in_binary(sort_in_binary(a, n, w), n, w)
```
结束
结束
结束
结束
结束
结束
结束
结束
结束
结束