对于给定的排列字典序编号，是否可能在O(1)时间内获取其中任意一个元素？

Question

对于给定的排列字典序编号，是否可能在O(1)时间内获取其中任意一个元素？

algorithmencryptionpermutationcombinatoricsnumber-theory

22

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

给定一个由 N 个元素组成的空间（即所有介于 0 和 N-1 之间的数字）。让我们看看在该空间上的所有排列，并将其称为 S。第 i 个 S 成员，可以标记为 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!。

现在，我已经知道如何根据索引号i获取排列，以及如何进行反转（获取给定排列的字典序编号）。但我想要更好的东西。

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

如果您只是在查看该空间上的随机排列，那么它会非常大，您甚至无法将整个排列存储在硬盘上，更别说按字典顺序计算每个项目。我想要的是能够对该排列进行项目访问，并获取每个项目的索引。也就是说，给定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)的成员），您输出加密块，该成员是在排列中原始块的索引号。解密时，您执行反向操作（查找块的索引号）。我相信这是以O(1)完成的，虽然我不确定，但无论如何速度非常快。

使用AES或任何其他块密码的问题在于它限制了您非常特定的N，并且可能仅捕获可能排列的一小部分，而我想能够使用任何我喜欢的N，并且可以在任何排列S[i]上进行项目访问。

是否可能在给定大小N和排列编号i的情况下获得O(1)的排列项访问？如果是，怎么做？

(如果我在这里得到编程答案，我希望它们是用Python编写的。)

更新：

一些人指出排列数本身非常巨大，仅仅读取这个数字就会使任务变得不可行。那么，我想修改我的问题：给定一个排列的词典序号的factoradic representation，是否有可能以O(尽可能小的)的时间得到排列中的任何项？

- Ram Rachum

2

O(1) 确实看起来非常雄心勃勃。 - Niklas B.

@RamRachum 我不同意你的看法，因为在枚举 10^10 个项之前是渐近最优的，因为它是O(N)，甚至比输入大小还要小。你可以在内存中构建排列，只需要另外40G的空间。 - Niklas B.

@RamRachum 检查：http://www.mathblog.dk/project-euler-24-millionth-lexicographic-permutation/ - Khaled.K

@KhaledAKhunaifer 我认为这个算法存在与我在评论中指出给phil_20686的回答相同的问题。在你找到想要的那个之前，它需要遍历排列中的每个项目。 - Ram Rachum

@RamRachum 如果你查看链接，在那篇文章的评论中，似乎有人提出了一些未经证实的想法。 - Khaled.K

显示剩余15条评论

5个回答

4

您的问题有些无意义，因为您想要表示所有可能的排列组合，一个任意排列索引的输入大小为log(N!)，其大小为Theta(NlogN)，因此，如果N非常大，仅读取排列索引的输入将需要太长时间，肯定比O(1)更长。也许可以以这样一种方式存储排列索引，即如果您已经存储了它，则可以在O(1)的时间内访问元素。但是，可能任何这种方法都等同于仅在连续内存中存储排列（其大小也为Theta(NlogN)），如果直接在内存中存储排列，则假设您可以进行O(1)存储器访问，则问题变得微不足道。（但是，您仍然需要考虑元素的位编码大小，这是O(log N)）。按照您的加密类比的精神，也许您应该根据某些属性指定一小部分排列，然后问是否可以对该小型子集进行O(1)或O(log N)元素访问。

- user2566092

2

编辑:

我误解了问题，但这并非是浪费。我的算法让我理解：排列的字典序编号的阶乘表示几乎与排列本身相同。实际上，阶乘表示的第一个数字与相应排列的第一个元素相同（假设您的空间由0到N-1的数字组成）。知道这一点，没有必要存储索引而不是排列本身。要了解如何将字典序编号转换为排列，请参阅下文。另请参见此维基百科链接有关Lehmer code。

原始帖子：

在S空间中，有N个元素可以填充第一个插槽，这意味着以0开头的元素有(N-1)!种。因此i / (N-1)!是第一个元素（称其为 'a'）。以0开始的S子集由（N-1）！个元素组成。这些是N{a}集合的可能排列方式。现在可以获取第二个元素：它是i（%((N-1)!)/(N-2)!）.重复该过程，您就得到了排列。

反转同样简单。从i = 0开始。获取排列的倒数第二个元素。构成最后两个元素的集合，并找到在其中的元素位置（它可能是第0个元素或第1个元素），让这个位置为j。然后i + = j*2！。重复此过程（您也可以从最后一个元素开始，但它始终是可能性中的第0个元素）。

类似Java的伪代码：

find_by_index(List N, int i){
    String str = "";
    for(int l = N.length-1; i >= 0; i--){
        int pos = i/fact(l);
        str += N.get(pos);
        N.remove(pos);
        i %= fact(l);
    }
    return str;
}

find_index(String str){
    OrderedList N;
    int i = 0;
    for(int l = str.length-1; l >= 0; l--){
        String item = str.charAt(l);
        int pos = N.add(item);
        i += pos*fact(str.length-l)
    }
    return i;
}

假设N是预排序的，find_by_index应该在O(n)内运行，而find_index是O(n*log(n))（其中n是N空间的大小）

- Kicsi

0

在维基百科上做了一些研究后，我设计了这个算法：

def getPick(fact_num_list):
    """fact_num_list should be a list with the factorial number representation, 
    getPick will return a tuple"""
    result = [] #Desired pick
    #This will hold all the numbers pickable; not actually a set, but a list
    #instead
    inputset = range(len(fact_num_list)) 
    for fnl in fact_num_list:
        result.append(inputset[fnl])
        del inputset[fnl] #Make sure we can't pick the number again
    return tuple(result)

显然，由于我们需要“挑选”每个数字，这不会达到O(1)。由于我们使用了一个for循环，因此假设所有操作都是O(1)，getPick将以O(n)运行。

如果我们需要将十进制转换为阶乘基数，这是一个辅助函数：

import math

def base10_baseFactorial(number):
    """Converts a base10 number into a factorial base number. Output is a list
    for better handle of units over 36! (after using all 0-9 and A-Z)"""
    loop = 1
    #Make sure n! <= number
    while math.factorial(loop) <= number:
        loop += 1
    result = []
    if not math.factorial(loop) == number:
        loop -= 1 #Prevent dividing over a smaller number than denominator
    while loop > 0:
        denominator = math.factorial(loop)
        number, rem = divmod(number, denominator)
        result.append(rem)
        loop -= 1
    result.append(0) #Don't forget to divide to 0! as well!
    return result

再次强调，由于 while 循环的存在，这段代码的时间复杂度为 O(n)。

总结一下，我们能够找到的最优时间复杂度是 O(n)。

PS：我不是以英语为母语的人，因此可能会出现拼写和措辞错误。提前道歉，并让我知道如果你有什么理解上的困难。

- SonicARG

0

所有正确的算法用于访问以factoradic格式存储的排列的第k项，必须读取前k个数字。这是因为，无论在前k个数中其他数字的值如何，未读数字是0还是取其最大值，都会产生差异。可以通过在两个并行执行中跟踪规范的正确解码程序来看到这一点。

例如，如果我们想解码排列1？0的第三位数字，则对于100，该数字为0，对于110，该数字为2。

- David Eisenstat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phil_20686 · Accepted Answer

做到这一点的秘诀是要“按阶乘计数”。

与 134 = 1 * 10 ^ 2 + 3 * 10 + 4 相同，134 = 5！+ 2 * 3！+ 2！=> 10210 阶乘表示法（包括 1！，不包括 0！）。如果您想表示 N！，则需要 N ^ 2 十进制数字。（对于每个阶乘数字 N，它可以容纳的最大数字为 N）。除了关于您称之为 0 的内容有点混淆外，此阶乘表示法正是排列的字典序号。

您可以使用此见解手动解决 Euler Problem 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 的第一百万个排列。

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

我不太清楚您想要做什么，但了解上述过程应该有所帮助。例如，很明显，字典序号表示可用作散列表中的键的排序。您可以通过从左到右比较数字来按顺序排列数字，因此一旦插入数字，您就不必计算阶乘。