寻求适用于大规模CSV行的确定性可逆置换隐写函数方案

要通过置换CSV行序隐藏秘密消息，核心是实现确定性、可逆的置换-整数映射——直接枚举所有置换在大行数（如10000行）下完全不可行，最优方案是利用**阶乘数制（Factoradic）**将置换与整数双向转换，时间复杂度O(n)（或优化到O(n log n)），完全无需枚举所有可能的置换。

核心原理：阶乘数制与置换的一一对应 #

n个元素的置换总数是n!，每个置换可以唯一对应到0~n!-1之间的一个整数（即置换的字典序排名），反之亦然。我们可以把比特消息转成这个范围内的整数，再映射为置换；解码时反向操作即可。

实现方案 #

1. 编码函数（原始行列表 + 比特消息 → 置换后行列表） #

步骤：

• 将比特消息转为十进制整数k（需保证k < n!，否则消息长度超出当前行数量的存储上限）
• 把k转换为阶乘数制表示（长度为n，数位从高位到低位对应(n-1)!到0!的系数）
• 基于原始有序列表，通过阶乘数制的数位逐步选取元素生成置换结果

def factorial(n):
    res = 1
    for i in range(2, n+1):
        res *= i
    return res

def bits_to_int(bits_str):
    return int(bits_str, 2)

def int_to_factoradic(k, n):
    factoradic = []
    for i in range(1, n+1):
        factoradic.append(k % i)
        k = k // i
    return factoradic[::-1]  # 反转得到高位到低位的阶乘数制

def encode(A, message):
    n = len(A)
    max_perms = factorial(n)
    max_bits = max_perms.bit_length() - 1
    
    if len(message) > max_bits:
        raise ValueError(f"Message too long: max {max_bits} bits for {n} rows")
    
    k = bits_to_int(message)
    if k >= max_perms:
        raise ValueError(f"Message value {k} exceeds max permutation index {max_perms - 1}")
    
    factoradic = int_to_factoradic(k, n)
    temp = A.copy()
    result = []
    
    for idx in factoradic:
        result.append(temp.pop(idx))
    
    return result

2. 解码函数（置换后行列表 → 原始比特消息） #

步骤：

• 对比原始有序列表，确定置换后每个元素在剩余列表中的位置，生成阶乘数制表示
• 将阶乘数制转换为整数k
• 把k转回二进制字符串，得到原始消息

def factoradic_to_int(factoradic):
    n = len(factoradic)
    res = 0
    for i in range(n):
        res += factoradic[i] * factorial(n - 1 - i)
    return res

def int_to_bits(k, target_length):
    return bin(k)[2:].zfill(target_length)

def decode(B, original_A):
    n = len(B)
    temp = original_A.copy()
    factoradic = []
    
    for elem in B:
        pos = temp.index(elem)
        factoradic.append(pos)
        temp.pop(pos)
    
    k = factoradic_to_int(factoradic)
    max_bits = factorial(n).bit_length() - 1
    # 返回补前导零到最大比特长度的结果，或按需裁剪
    return int_to_bits(k, max_bits)

针对超大行数（如10000行）的关键优化 #

优化1：替换O(n)的索引查找 #

上述解码中list.index()是O(n)操作，n=10000时总时间复杂度会到O(n²)，严重拖慢速度。可以用有序列表（SortedList）或线段树维护剩余元素的索引，将查找和删除操作降到O(log n)：

from sortedcontainers import SortedList

def decode_optimized(B, original_A):
    n = len(B)
    # 预存原始元素到索引的映射
    elem_to_orig_idx = {elem: idx for idx, elem in enumerate(original_A)}
    # 用SortedList维护当前剩余的原始索引
    remaining_indices = SortedList(range(n))
    factoradic = []
    
    for elem in B:
        orig_idx = elem_to_orig_idx[elem]
        # 找到当前剩余列表中orig_idx的位置（即阶乘数制的数位）
        pos = remaining_indices.index(orig_idx)
        factoradic.append(pos)
        remaining_indices.remove(orig_idx)
    
    k = factoradic_to_int(factoradic)
    max_bits = factorial(n).bit_length() - 1
    return int_to_bits(k, max_bits)

如果不想依赖第三方库，可以自行实现线段树来支持动态索引的排名查询与删除。

优化2：避免超大整数处理 #

当n≥20时，n!已经超出64位整数范围，n=10000时n!更是一个数万位的大数，无法直接存储。此时可以跳过十进制整数转换，直接在比特流和阶乘数制之间双向映射，无需处理超大整数：

• 编码时：逐位处理比特消息，直接计算阶乘数制的每个数位
• 解码时：将阶乘数制的数位直接转换为比特流，无需合并为大数

优化3：分块存储 #

如果CSV行数极大但消息较短，可以将行划分为多个小模块，每个模块用自身的置换存储部分消息。比如把10000行分成100个100行的块，每个块可存储约528比特（log2(100!)≈528），既避免处理超大阶乘，也降低单块的计算压力。

示例验证 #

用题目中的测试案例验证：

A = [1,2,3,4,5]
# 对应置换[2,1,3,4,5]的整数是1，二进制为'000001'（6比特）
message = '000001'
B = encode(A, message)
print(B)  # 输出: [2, 1, 3, 4, 5]

recovered_msg = decode(B, A)
print(recovered_msg)  # 输出: '000001'

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