algorithm - 给定一个排列的字典序号，是否有可能在 O(1) 中得到其中的任何项目

Question

我想知道下面解释的任务在理论上是否可行，如果可以，我该怎么做。

您将获得 N 的空格元素(即 0 和 N-1 之间的所有数字。)让我们看看该空间上所有排列的空间，并将其称为 S . i S 的第 3 个成员，可以标记为S[i] , 是字典序号 i 的排列.

例如，如果 N是 3，那么 S是这个排列列表:

S[0]: 0, 1, 2
S[1]: 0, 2, 1
S[2]: 1, 0, 2
S[3]: 1, 2, 0
S[4]: 2, 0, 1
S[5]: 2, 1, 0

(当然，当查看一个大的 N 时，这个空间变得非常大，确切地说是 N!。)

现在，我已经知道了how to get the permutation by its index number i , and I already know how to do the reverse (get the lexicographic number of a given permutation.)但我想要更好的东西。

一些排列本身可能是巨大的。例如，如果您正在查看 N=10^20 . (S 的大小将是 (10^20)!，我相信这是我在 Stack Overflow 问题中提到的最大数字 :)

如果您只是查看该空间上的随机排列，那么它会太大以至于您无法将整个内容存储在硬盘上，更不用说按字典序号计算每个项目了。我想要的是能够对该排列进行项目访问，并获得每个项目的索引。也就是说，给定 N和 i要指定排列，有一个函数接受一个索引号并找到驻留在该索引中的数字，另一个函数接受一个数字并找到它所在的索引。我想在 O(1) 中这样做，所以我不需要存储或迭代排列中的每个成员。

疯了，你说？不可能的？那可能。但是考虑一下:像 AES 一样的分组密码本质上是一种排列，它几乎可以完成我上面概述的任务。 AES 的 block 大小为 16 字节，这意味着 N是 256^16大约是 10^38 . ( S 的大小，并不重要，是一个惊人的 (256^16)! ，或大约 10^85070591730234615865843651857942052838 ，这超过了我最近的“堆栈溢出中提到的最大数字”的记录:)

每个 AES 加密 key 在 N=256^16 上指定一个排列。 .这种排列不能完整地存储在你的计算机上，因为它的成员比太阳系中的原子还多。但是，它允许您访问项目。通过使用 AES 加密数据，您可以逐 block 查看数据，并且对于每个 block (range(N) 的成员)，您输出加密 block ，它是 range(N) 的成员即排列中原始 block 的索引号。当你解密时，你正在做相反的事情(找到一个 block 的索引号。)我相信这是在 O(1) 中完成的。 ，我不确定，但无论如何它都非常快。

使用 AES 或任何其他分组密码的问题在于它将您限制在非常具体的 N 上。 ，并且它可能只捕获了一小部分可能的排列，而我希望能够使用任何 N我喜欢，并且可以对任何排列进行项目访问 S[i]是我喜欢的。

有没有可能得到O(1)排列上的项目访问，给定大小 N和排列编号i ?如果是这样，怎么做？

(如果我有幸在这里得到代码答案，如果他们会在 Python 中，我将不胜感激。)

更新 :

一些人指出了一个可悲的事实，即排列数字本身会如此巨大，以至于仅读取数字会使任务不可行。然后，我想修改我的问题:可以访问 factoradic representation排列的字典序号，是否有可能在 O(尽可能小)中得到排列中的任何项目？

Answer 1

这样做的秘诀是“计算基本阶乘”。

同理134 = 1*10^2+3*10 + 4, 134 = 5! + 2 * 3! + 2! => 10210 采用阶乘符号(包括 1!，排除 0!)。如果要表示 N!，则需要 N^2 以十位为基数。 (对于每个阶乘数字 N，它可以容纳的最大数字是 N)。对你所说的 0 有点困惑，这个阶乘表示正是排列的字典序号。

您可以使用此见解手动解决欧拉问题 24。所以我会在这里做，你会看到如何解决你的问题。我们想要 0-9 的百万分之一排列。在阶乘表示中，我们取 1000000 => 26625122。现在要将其转换为排列，我取数字 0、1、2、3、4、5、6、7、8、9，第一个数字是 2，即是第三个(可能是 0)，所以我选择 2 作为第一个数字，然后我有一个新列表 0、1、3、4、5、6、7、8、9，我取第七个数字，即8 等，我得到 2783915604。

但是，这假设您从 0 开始您的词典排序，如果您实际上从 1 开始，则必须从中减去 1，得到 2783915460。这确实是数字 0-9 的百万分之一。

您显然可以反转此过程，因此可以轻松地在字典序数和它所代表的排列之间进行前后转换。

我不完全清楚你想在这里做什么，但理解上述过程应该会有所帮助。例如，很明显，词典数字表示可以用作哈希表中的键的顺序。而且您可以通过从左到右比较数字来订购数字，因此一旦您插入了一个数字，您就不必计算它的阶乘。