如何编码项目列表并指定顺序

Question

我不确定问这个问题的最佳方式，所以让我先举个例子。

假设我有一个可能项目的完整列表（i1、i2、i3、i4、.... i128）。我想要的是指定一个子列表（我们称之为列表 A），它指定列表中的项目以及列表的顺序。现在假设我想以尽可能小的方式对其进行编码。假设列表 A 如下：

i1, i2, i5, i20, i50, i80, i103, i121

如果我知道我的项目总是按顺序排列，那么我想我可以轻松地制作一个位数组，其中 1 表示项目存在，0 表示不存在。在我的示例中，我有 128 个可能的项目，因此我可以用 16 个字节表示存在的内容。所以列表 A 将是

1100100000000000000100.......
In Bytes: C8 00 10 00 00 00 40 00 .....

但是现在，我怎样才能以不使用 8 个字节的方式表达顺序？

我意识到对于这个例子，通过将每个项目分配给特定值然后按我想要的顺序放置这些值来按顺序编码列表会减少数据，但是如果我的列表大于16 项，然后我将开始使用更多数据来对它们进行编码。

是否有我没有想到的更好的解决方法？我希望我所说的是有道理的。如果我能澄清任何问题，请告诉我，并在此先感谢您的帮助！

Answer 1

将排列编码为 factoradic integer。对于许多项目，您将需要大量例程。在最坏的情况下需要 90 个字节，其中您有 128 个项目的排列。请注意，使用每个项目 7 位来简单地存储序列需要 112 个字节。

在显示的只有八个项目的情况下，需要两个字节来对排列进行编码。尽管位图有 16 个字节，但总共有 18 个字节。而不是直接对值进行编码的七个字节。

总的来说，您的序列仅限于非重复值这一事实不会给您带来很多好处。