algorithm - 如何生成排列？

Question

我的问题是:给定一个长度为 n 的列表 L 和一个满足 0 <= i < n! 的整数 i，如何编写一个函数 perm(L, n) 来生成 L 在 O 中的第 i 个排列(n) 时间？我所说的第 i 个排列只是某些实现定义的排序中的第 i 个排列，它必须具有以下属性:

1. 对于任意 i 和任意 2 个列表 A 和 B，perm(A, i) 和 perm(B, i) 都必须将 A 和 B 的第 j 个元素映射到 A 的相同位置的元素和 B.

2. 对于任何输入 (A, i), (A, j) perm(A, i)==perm(A, j) 当且仅当 i==j 时。

注意:这不是作业。事实上，我在 2 年前解决了这个问题，但我完全忘记了如何解决，这让我很痛苦。此外，这是我在解决方案中所做的失败尝试:

def perm(s, i):
  n = len(s)
  perm = [0]*n
  itCount = 0
  for elem in s:
    perm[i%n + itCount] = elem
    i = i / n
    n -= 1
    itCount+=1
  return perm

另请注意:O(n) 要求非常重要。否则你可以只生成 n!所有排列的大小列表，只返回它的第 i 个元素。

Answer 1

def perm(sequence, index):
    sequence = list(sequence)
    result = []
    for x in xrange(len(sequence)):
        idx = index % len(sequence)
        index /= len(sequence)
        result.append( sequence[idx] )
        # constant time non-order preserving removal
        sequence[idx] = sequence[-1]
        del sequence[-1]
    return result

基于洗牌的算法，但我们每次取数字的最低有效部分来决定取哪个元素而不是随机数。或者，将其视为转换为任意基数的问题，只是基数名称会随着每个额外的数字而缩小。