Ram*_*hum 22 encryption algorithm permutation combinatorics number-theory
我想知道下面解释的任务是否在理论上是可行的,如果是这样,我怎么能做到.
给你一个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中排列任何项目(尽可能小)？
这样做的秘诀是"算入基因因子".
同样地,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,得到2783915460.这确实是数字0-9的百万位排列.
显然,您可以撤消此过程,因此可以在lexiographic数字和它所代表的排列之间轻松地前后转换.
我不完全清楚你想在这里做什么,但理解上述程序应该有所帮助.例如,它清楚地表明,lexiographic数字表示可以用作哈希表中的键的顺序.你可以通过比较从左到右的数字来订购数字,所以一旦你插入了一个数字,你就不需要算出它的因子.
你的问题有点没有实际意义，因为任意排列索引的输入大小具有大小 log(N!) （假设你想表示所有可能的排列），即 Theta(N log N) ，所以如果 N 真的很大，那么就读取排列索引的输入将花费太长时间，肯定比 O(1) 长得多。可以以这样的方式存储排列索引：如果您已经存储了它，那么您可以在 O(1) 时间内访问元素。但可能任何这样的方法都相当于仅将排列存储在连续内存中（也具有 Theta(N log N) 大小），并且如果将排列直接存储在内存中，那么假设您可以执行 O(1 ）内存访问。（但是，您仍然需要考虑元素的位编码的大小，即 O(log N)）。
本着加密类比的精神，也许您应该根据某些属性指定一个小的排列子集，并询问该小子集是否可以进行 O(1) 或 O(log N) 元素访问。