求随机化数组的最小压缩表示R及还原方程E的技术方案

给定任意长度、任意值的数组，需构建还原方程E，为数组的随机化输出O找到简化（压缩）表示R，满足E(R)=O。

示例场景 #

输入长度为10、值与索引对应的排序数组Array=[0,1,2,3,4,5,6,7,8,9]，随机化后的输出数组为[9,5,8,2,1,0,6,3,4,7]。需要找到R，将其应用于排序数组后得到该随机化数组。

R的约束条件 #

• R的内存占用必须小于直接存储索引数组的大小
• R不能是LZ77、LZSS这类直接压缩输入的产物，必须是针对随机顺序的新型表示，而非输入的衍生形式
• 与原输入相比，平均压缩比至少达到2:1
• 对于给定长度的数组，R的内存大小固定。例如：若10元素数组的R占用3字节，则所有10元素的随机数组对应的R都必须是3字节

补充说明 #

• R的存储大小可随数组长度线性增长，若能实现无增长则更佳
• 允许R仅对长度大于阈值X（如数百或数千）的数组实现压缩，实际需求针对数十亿级长度的数组
• 仅关注数组元素的顺序（索引），无需关注元素值，可假设输入数组的值均为代表其他索引的整数

初步思路的局限 #

曾考虑用随机数生成器作为还原方程E，将随机数种子作为R。但反向从输出O推导种子没有高效的数学方法，暴力匹配完全不可行，因此接受任何满足约束的可行方案。

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