如何生成排列？

Question

我的问题是：给定一个长度为 n 的列表 L 和一个整数 i，使得 0 <= i < n!，如何编写函数 perm(L, n) 在 O(n) 时间内生成 L 的第 i 个排列？我所说的第 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。

注意：这不是家庭作业。事实上，我两年前就解决了这个问题，但我完全忘记了怎么解决的，这让我很痛苦。另外，这是我在解决方案中所做的一次失败的尝试：

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

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

Answer 2

你能使用factoradics吗？您可以通过这篇MSDN 文章找到说明。

更新：我写了一个 MSDN 算法的扩展，它找到了 n 个事物的第 i 个排列 r一次，即使 n != r。

Answer 3

计算简约方法（用 C 风格伪代码编写）：

function perm(list,i){
    for(a=list.length;a;a--){
        list.switch(a-1,i mod a);
        i=i/a;
    }
    return list;
}

请注意，依赖于从原始列表中删除元素的实现往往会在 O(n^2) 时间内运行，在给定特殊条件的情况下，最多为 O(n*log(n))树形列表实现设计用于快速插入和删除列表元素。

上面的代码并没有缩小原始列表并保持其顺序，只是将一个元素从末尾移动到空位置，仍然在索引和排列之间建立了完美的 1:1 映射，只是稍微混乱了一点，但是在纯 O 中(n) 时间。

Answer 4

所以，我想我终于解决了这个问题。在阅读任何答案之前，我将在这里发布我自己的答案。

def perm(L, i):
  n = len(L)
  if (n == 1):
    return L
  else:
    split = i%n
    return [L[split]] + perm(L[:split] + L[split+1:], i/n)

Answer 5

有n个！排列。第一个字符可以通过 n 种方式从 L 中选择。这些选择中的每一个都留下 (n-1)！其中的排列。所以这个想法足以建立订单。一般来说，你会弄清楚你处于哪个部分，选择适当的元素，然后在较小的 L 上递归/循环。

这个正确工作的论点是通过对序列长度的归纳。 （草图）对于长度为 1 来说，这是微不足道的。对于长度为 n 的情况，您可以使用上述观察将问题分为 n 个部分，每个部分都有一个关于长度为 (n-1) 的 L' 的问题。通过归纳，所有 L 都被正确构造（并且在线性时间内）。那么很明显我们可以使用 IH 来构造长度 n 的解。