22

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

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

（当然，当看一个 big 时N，这个空间变得非常大，N!确切地说。）

现在，我已经知道如何通过索引号获取排列i，并且我已经知道如何进行相反的操作（获取给定排列的字典序号。）但我想要更好的东西。

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

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

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

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

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

是否可以在给定大小和排列数O(1)的排列上获得项目访问权限？如果是这样，怎么做？Ni

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

更新：

一些人指出了一个可悲的事实，即排列数字本身会如此巨大，以至于仅读取数字会使任务不可行。然后，我想修改我的问题：如果可以访问排列的字典序数的阶乘表示，是否有可能在 O 中获得排列中的任何项目（尽可能小）？

4

5 回答 5

5

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

同理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 的百万分之一。

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

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

于 2014-05-12T10:56:10.020 回答
4

您的问题有点没有实际意义，因为您的任意排列索引的输入大小具有大小 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) 元素访问。

于 2014-05-06T19:23:06.190 回答
2

编辑：

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

原帖：

在S空间中有N个元素可以填满第一个槽，也就是说有(N-1)个！以 0 开头的元素。所以 i/(N-1)！是第一个元素（我们称之为'a'）。S 的以 0 开头的子集由 (N-1) 个组成！元素。这些是集合 N{a} 的可能排列。现在你可以得到第二个元素：它的 i(%((N-1)!)/(N-2)!)。重复这个过程，你就得到了排列。

反向同样简单。从 i=0 开始。获取排列的倒数第二个元素。制作一组最后两个元素，并找到元素在其中的位置（它的第 0 个元素或第 1 个元素），让我们将此位置称为 j。然后 i+=j*2!。重复该过程（您也可以从最后一个元素开始，但它始终是可能性的第 0 个元素）。

Java-ish 伪代码：

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;
}

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

于 2014-05-10T23:01:49.863 回答
0

所有用于访问以因子形式存储的排列的第 k 项的正确算法都必须读取前 k 位。这是因为，不管前k个中的其他数字的值如何，未读数字是0还是取其最大值是不同的。通过在两个并行执行中跟踪规范的正确解码程序可以看出这种情况。

例如，如果我们要解码排列 1?0 的第三个数字，那么对于 100，该数字为 0，而对于 110，该数字为 2。

于 2014-05-15T20:53:56.203 回答
0

在Wikipedia进行一些研究后，我设计了这个算法：

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) 中运行。

如果我们需要从基数 10 转换为阶乘基数，这是一个辅助函数：

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

同样，由于whiles，这将在 O(n) 中运行。

总而言之，我们能找到的最佳时间是O(n)。

PS：我的母语不是英语，所以可能会出现拼写和措辞错误。提前道歉，如果您无法解决问题，请告诉我。

于 2014-05-14T19:14:50.237 回答