给定排列的词典编号,是否可以在O(1)中获取其中的任何项目

我想知道下面解释的任务是否在理论上是可行的,如果是这样,我怎么能做到.

给你一个N元素空间(即0和之间的所有数字N-1.)让我们看看那个空间上所有排列的空间,然后调用它S.可以标记的i第th个成员是带有词典编号的排列.SS[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!确切地说.)

现在,我已经知道如何通过其索引号来获得排列i,并且我已经知道如何反转(得到给定排列的词典编号.)但我想要更好的东西.

一些排列本身可能很大.例如,如果你正在看N=10^20.(的大小S将是(10^20)!我相信这是我在一个堆栈溢出问题提起过的最大号:)

如果你只是在那个空间上看一个随机的排列,那么你将无法将整个东西存储在你的硬盘上,更不用说通过词典编号来计算每个项目了.我想要的是能够对该排列进行项目访问,并获得每个项目的索引.也就是说,给定N和i指定一个排列,有一个函数接受一个索引号并找到该索引中的数字,另一个函数接受一个数字并找到它所在的索引.我想这样做O(1),所以我不需要在排列中存储或迭代每个成员.

你说疯了吗？不可能？那可能.但请考虑一下:像AES这样的分组密码本质上是一种排列,它几乎完成了我上面概述的任务.AES具有16个字节的块大小,这意味着N是256^16它是围绕10^38.(S重要的是,它的大小是一个惊人的(256^16)!,或者说是围绕着10^85070591730234615865843651857942052838,这超过了我最近在"Stack Overflow上提到的最大数量"的记录:)

每个AES加密密钥指定单个排列N=256^16.这种排列无法整体存储在您的计算机上,因为它的成员数量多于太阳系中的原子数.但是,它允许您访问项目.通过使用AES加密数据,您可以逐块查看数据,并为每个块(成员range(N))输出加密块,其成员range(N)位于排列中原始块的索引号中.当你正在解密时,你正在反向(找到一个块的索引号.)我相信这已经完成了O(1),我不确定,但无论如何它都非常快.

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

O(1)在给定大小N和排列数的情况下,是否可以对置换进行项目访问i？如果是这样,怎么样？

(如果我很幸运能在这里得到代码答案,我会很感激他们是否会使用Python.)

更新:

有些人指出了一个可悲的事实,即排列数本身就是如此庞大,只要读取数字就会使任务变得不可行.然后,我想修改我的问题:既可以访问排列词典编号的事实表示,是否可以在O中排列任何项目(尽可能小)？