在 O(n) 中获取作为唯一给定索引的函数的排列

我想要一个函数get_permutation给定一个列表l和一个索引i，返回一个排列l这样排列对于所有人来说都是唯一的i大于0并低于n! (where n = len(l)).

I.e. get_permutation(l,i) != get_permutation(l,j) if i!=j对全部i, j s.t. 0 <= i and j < len(l)!).

此外，这个函数必须运行在O(n).

例如，如果不是指数顺序，此函数将符合要求：

def get_permutation(l, i):
     return list(itertools.permutations(l))[i]

有人对上述问题有解决方案吗？

EDIT:我想要排列从索引不是排列中的索引

如果您不关心哪些排列获得哪些索引，则 O(n) 解决方案成为可能如果我们认为任意整数的算术运算是 O(1).

例如，参见论文“线性时间内的排序和取消排序排列 http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf”温迪·梅尔沃德和弗兰克·鲁斯基着。

简而言之，有两个想法。

(1)考虑费舍尔-耶茨洗牌 http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle生成随机排列的方法（下面的伪代码）：

p = [0, 1, ..., n-1]
for i := 0 upto n-1:
    j := random_integer (0, i)
    exchange p[i] and p[j]

这种变换是单射的：如果我们给它不同的随机整数序列，它保证产生不同的排列。因此，我们用非随机整数替换随机整数：第一个是 0，第二个是 0 或 1，...，最后一个可以是 0 到 n-1 之间的任何整数。

(2) 有n个！ n 阶排列。我们现在要做的就是将一个从 0 到 n!-1 的整数写入阶乘数制 http://en.wikipedia.org/wiki/Factorial_number_system：最后一位总是0，前一位是0或1，...，第一位数字有从0到n-1的n种可能性。因此，我们将获得一个唯一的序列来提供上述伪代码。

现在，如果我们认为将数字除以 1 到 n 之间的整数是 O(1) 运算，那么将数字转换为阶乘系统就是 O(n) 这样的除法。严格来说，这是不正确的：对于大n，数字n！包含 O(n log n) 个二进制数字，除法的成本与位数成正比。

在实践中，对于小 n，O(n^2) 或 O(n log n) 方法对排列进行排序或取消排序，并且还需要 O(2^n) 或 O(n!) 内存来存储一些预先计算的值，可能比涉及整数除法的 O(n) 方法更快，后者在现代处理器上是相对较慢的操作。 对于 n 足够大，使得 n!不适合机器字，“如果 n 阶！整数运算为 O(1)，则为 O(n)”参数将停止工作。因此，如果您不坚持理论上 O(n)，那么无论小 n 还是大 n，您都可能会更好。