0-99无重复随机整数序列的最优无损压缩算法及Python实现咨询

核心逻辑 #

你说的没错，单个随机数确实没法压缩，但0-99的全排列本质上只有100!种可能的顺序——我们可以把每个排列映射成一个唯一的整数（范围是0到100!-1），这个整数的二进制表示就是理论上最小的压缩结果（约525比特，合66字节），完全没有冗余，是最优的无损压缩方式。

具体实现思路 #

1. 排列转整数（压缩） #

用莱康德编码（Lehmer Code）实现：遍历排列里的每个元素，计算当前还没被用的数字中，比当前元素小的数字个数，把这些数组成一个序列，再把这个序列转换成一个十进制整数（这个整数就是该排列的唯一标识）。

举个小例子：排列[2,0,1]，第一步未使用的数是[0,1,2]，比2小的有2个，记2；第二步未使用的是[0,1]，比0小的有0个，记0；第三步只剩1，记0。得到序列[2,0,0]，转换成整数是2*2! + 0*1! + 0*0! =4。

2. 整数转排列（解压缩） #

把整数还原成莱康德序列，再逐步还原原排列：从0到99的完整数字列表开始，根据序列里的每个数，取出对应位置的元素，剩下的数字继续处理，直到还原出完整排列。

Python 实现代码 #

下面是简化版代码，不需要额外依赖库，适合非专业人士直接用：

压缩函数 #

import math

def permutation_to_int(perm):
    # 预先计算0!到99!的阶乘表
    factorials = [math.factorial(i) for i in range(100)]
    unused = list(range(100))
    result = 0
    for num in perm:
        # 找到当前数字在未使用列表中的位置
        idx = unused.index(num)
        # 累加对应的阶乘权重
        result += idx * factorials[len(unused)-1]
        # 移除已使用的数字
        unused.pop(idx)
    return result

解压缩函数 #

def int_to_permutation(n):
    factorials = [math.factorial(i) for i in range(100)]
    unused = list(range(100))
    perm = []
    # 从最大的阶乘开始反向计算
    for i in range(99, -1, -1):
        fact = factorials[i]
        # 计算当前数字在未使用列表中的索引
        idx = n // fact
        perm.append(unused[idx])
        unused.pop(idx)
        # 更新剩余数值
        n = n % fact
    return perm

使用示例 #

# 生成一个测试用的0-99全排列
import random
original_perm = list(range(100))
random.shuffle(original_perm)

# 压缩排列为整数
compressed_num = permutation_to_int(original_perm)
print(f"压缩后的整数：{compressed_num}")
print(f"压缩后的字节数：{compressed_num.bit_length() // 8 + 1}")  # 约66字节，符合理论最优值

# 解压缩回原排列
restored_perm = int_to_permutation(compressed_num)
print(f"原排列与解压缩结果是否一致：{original_perm == restored_perm}")

实用小提示 #

• Python原生支持超大整数，不用担心100!这种巨量数值的溢出问题。
• 如果要存到文件里，把整数转成二进制字节串更省空间：用compressed_num.to_bytes((compressed_num.bit_length() +7)//8, byteorder='big')转成字节串，读取时用int.from_bytes(读取的字节串, byteorder='big')转回来即可。

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