如何以空间高效方式存储与检索20个对象数据集的显示顺序？

嘿，你这个观察太到位了！用20个5比特无符号整数（加起来100比特）来存储这20个对象的排序，确实有点空间浪费——毕竟每个5比特数能取0-31，32^20的可能值远大于实际存在的20!种排列，咱们完全可以用更紧凑的方式来存。

先给你算个直观的对比：

• 20! 大概是2.43×10¹⁸，转换成二进制的话只需要62比特（因为2⁶¹≈2.3×10¹⁸，2⁶²≈4.6×10¹⁸），比原来的100比特省了近40%的空间。

下面给你两种最实用的高效存储方式，都是工业界常用的思路：

1. 直接用一个大整数搞定（阶乘编码映射） #

这里要用到阶乘数系统，它能把每一种唯一的排列，映射到一个唯一的整数（业内叫“排列的阶乘展开数”）。具体怎么操作呢？

举个例子：假设你要存的排序是原数组索引的排列，比如[5,3,12,...]，咱们一步步算对应的整数：

• 看排列里的第一个元素，数一下原数组里比它小、还没被选过的元素个数，记为a₀（范围0-19）
• 第二个元素，数剩下19个元素里比它小的个数，记为a₁（范围0-18）
• 以此类推，直到第20个元素，剩下的只有它自己，所以a₁₉=0

然后把这些a值代入公式：
N = a₀×19! + a₁×18! + ... + a₁₈×1! + a₁₉×0!

得到的N就是唯一对应这个排列的整数。反过来，给你N，你也可以通过不断除以k!（k从19到0）取余数，还原出每个a值，进而把排列找回来。

这种方式只需要一个62比特的整数——大部分编程语言里的uint64_t（或者Python里的普通整数）都能轻松存下，空间占用最小，转换逻辑也成熟。

2. 优化版的数组存储（可变比特长度） #

如果你还是习惯用数组形式存储，也可以给每个元素“量身定制”比特数，不用统一用5比特：

• 第一个排序索引要区分20种可能，得用5比特（2⁴=16不够，2⁵=32刚好）
• 第二个剩下19种，还是5比特
• ...
• 第17个剩下4种，只需要2比特（2²=4）
• 第18个剩下3种，2比特足够
• 第19个剩下2种，1比特就行
• 第20个只剩1种，不用占空间

加起来总共是5×16 + 2×2 +1 = 85比特，比原来的100比特省了不少。不过这种方式需要处理可变长度的比特读写，不如直接存大整数方便。

附个实用代码示例（Python） #

如果你的场景允许一点点计算开销，直接用阶乘编码的大整数绝对是最优解。给你写个简单的Python实现，用来在排列和整数之间转换：

import math

def permutation_to_int(perm):
    n = len(perm)
    result = 0
    used = [False] * n
    for i in range(n):
        # 统计当前元素在未使用元素中的排名（比它小的未使用数的个数）
        count = sum(1 for j in range(perm[i]) if not used[j])
        result += count * math.factorial(n - 1 - i)
        used[perm[i]] = True
    return result

def int_to_permutation(num, n):
    perm = []
    used = [False] * n
    for i in range(n):
        fact = math.factorial(n - 1 - i)
        count = num // fact
        num = num % fact
        # 找到第count个未被使用的索引
        idx = 0
        while count >= 0:
            if not used[idx]:
                if count == 0:
                    break
                count -= 1
            idx += 1
        perm.append(idx)
        used[idx] = True
    return perm

比如你把排序后的索引数组传进permutation_to_int，得到的整数就是你要存的内容；需要还原的时候，把整数和20传给int_to_permutation，就能拿回排序顺序啦。

内容的提问来源于stack exchange，提问作者Drew