我正在寻求关于实现有序列表的最高效存储的建议，即列表的最小存储。
一个由256个唯一项目组成的有序列表，其中每个项目都是从0到255的唯一数字，标准情况下需要2^16位数据进行存储，2^8个位置，每个位置都有2^8的值。
然而，这些信息应该可以存储在2^15位附近。
第二个项目，而不是在256的第二位，可以被视为剩余255中的下一个，下一个项目是剩余254中的下个，等等。
这是不需要存储排序列表中最后一个项目的详细信息的延续，因为默认情况下该项目必须位于最后一个位置。
在这种情况下，你可以简单地看到，你可以有2^8-1的位置，每个位置都有2^8的值，小于2^16。
那么，这是如何减少到2^15+1位存储的呢。或者有证据表明情况并非如此？如果有证据，我希望它不会说需要2^16位的存储空间，因为我刚刚证明了这是错误的！
希望我只是不知道在这个主题上识别工作的术语。
有人能就此事提出工作建议吗？
谢谢你抽出时间。
格伦
在将问题澄清为256项的某个特定排列(特别是从0到255的8位数字)的存储后，我更新了我的答案。下面是先前的讨论，以供后人参考。
回答
1684位。
解释
在这种情况下，最清晰的分析来自编码和信息熵。同样，我们使用了鸽子洞原理：为了唯一地确定特定的排列，我们必须至少有尽可能多的编码信息来编码。
举个例子可能会有所帮助：考虑一个由256个数字组成的列表，每个数字都是一个8位数字。第一个项目有256个可能的值，第二个项目有，第三个项目也有，依此类推。总体而言，我们有256^256条可能的消息，因此我们至少需要256^256个可能编码。为了确定所需的比特数，我们可以简单地取其以2为底的对数，log2(256^256)=256*log2(256)=2256*log2)(2^8)=256*6=2^11，因此我们可以看到，要对该列表进行编码，我们只需要2^11，或2048个比特。您可能会注意到，这与每个项目取8位并乘以项目数相同。你最初的问题是不正确的，因为你认为它需要2^8位，所以是一个256位的整数，可以存储从0到~10^77的值。
有了这一认识，我们就把注意力转向眼前的问题。第一个项目有256种可能性，然后第二个项目有255种可能性，第三个项目有254种可能性，等等，直到最后一个项目只有1种可能性。总的来说，我们有256个！可能性，所以我们至少需要256个！编码。同样，我们使用以2为底的对数来确定我们需要多少位，因此我们需要log2(256！)位。对数的一个很好的特性是，它们将乘积转化为和，因此log2(256！)=log2(256+log2(255)+log 2(254)+…+log2(2)+log2(1)。这类似于对256个项目中的每一个项目使用8个比特，但在这里，由于每个项目具有逐渐减少的信息，因此需要更少的比特。还要注意，log2(1)是0，这与您的观察结果相对应，即您不需要任何信息来编码最后一项。总的来说，当我们执行这个求和时，我们最终得到1683.996…，所以我们需要1684位来编码这些有序列表。一些可变长度编码可能会更低，但它们的平均值永远不会低于log2(256！)位。
提出使用1684位的编码并不简单，但这里有一种方法比原始的完整存储更高效。我们可以注意到，前128个项目中的每一个都有129到256种可能性，并用8位对这些项目中的每个进行编码。接下来的64个项目每个都有65到128个可能性，所以我们可以用7位对这些项目中的每个进行编码。继续，我们最终使用(128×8)+(64×7)+(32×6)+(16×5)+(8×4)+(4×3)+(2×2)+(1×1)+(1*0)＝1793位来存储列表。
澄清前讨论
如果你对编码感兴趣的只是一个由256个唯一项目组成的有序列表，其中每个项目都是一个8位整数，那么你可以用1位来完成：0表示你有这个列表，1表示你没有，因为只有一个可能的列表满足这些条件。
如果你试图在内存中存储任何东西，你需要的内存配置至少与不同的选项一样多(否则，根据鸽子洞原则，至少有两个选项你无法区分)。假设由"；有序的"；你的意思是，它们严格地递增或递减，一个8位整数的n元素有序列表，没有重复，有256个选择n个可能的选项(因为只有一个可能的配置，有序的配置)。求和256，在n的所有可能值(即0到256)中选择n，得到2^256或2^(2^8)。因此，一个完美的编码方案可以只使用2^8位来存储这种特定类型的列表，但不能对任何其他类型的列表进行编码。
编辑：如果你想阅读更多关于这类东西的内容，请阅读信息论。
编辑：考虑这种编码的一种更简单的方法是这样的：我们知道列表是有序的，所以如果我们知道其中有哪些项目，那么我们就知道它们的顺序，所以我们只需要知道列表中有哪些项目。有256个可能的项目(0到255)，如果我们假设列表中的项目是唯一的，那么每个项目要么在列表中，要么不在列表中。对于每个项目，我们使用1位来存储它是否在列表中(因此，如果列表包含0，则位0记录；如果列表包含1，则位1记录；等等，如果列表含有255，则位255记录)。Tada，我们已经用256=2^8位存储了关于这个256元素字节数组的所有信息。
编辑：让我们来看看类似的情况。我们有一个有序的、唯一的列表，最多包含4个项目，每个项目都是2位。我们将写出所有可能的情况：[]，[0]，[1]，[2]，[3]，[0,1]，[0,2]，[0,3]，[2,3]，[0,1,2]，[0.1,3]，[00,1,3]，[0.2,3]，[02,3]，[1,2]，[1，2]，[1，3]，[1，23]，[01,2,3]。这些是仅的可能列表，其中每个元素是两位，元素是唯一的，并且元素按升序排列。请注意，我不能仅仅通过去掉[0,1,2,3]的3来提高它的效率，因为我还需要将它与[0,1,2]区分开来。问题是，问你需要多少空间来"；存储"；脱离上下文的东西几乎是无法回答的。如果你只想存储足够的信息来恢复它(即，你想要无损压缩)，并且你假设你知道这些属性，你可以得到你想要的压缩比。例如，如果您给我一个包含从0到1000000的每个元素的有序列表，并且只包含一次，即使将该列表直接存储在内存中需要~2^40位，您也可以从已知属性和0和1000000这两个数字中恢复该列表，总共40位。