如何生成排列？

Question

我的问题是：给定一个长度为n的列表L和一个整数i，其中0 <= i < n!，如何编写一个函数perm(L, n)，以O(n)时间生成L的第i个排列？我的意思是L的第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 个元素。

- CromTheDestroyer

---

你肯定是指 perm(L, i) 而不是 perm(L, n) 吧？ - I GIVE CRAP ANSWERS

哦，如果A字符串包含多个相同符号的话，你的第二点不就被违反了吗？ - I GIVE CRAP ANSWERS

@jlouis 实际上，如果参数i被指定为在0到不同排列数量之间变化，并且函数必须仅生成独特的排列，则这将成为一个有趣但相当困难的问题。 - Pascal Cuoq

jlouis: 嗯，这是真的。好吧，假设所有元素都是不同的。 - CromTheDestroyer

Pascal Cuoq：参数i已经在0到不同排列数-1之间的范围内指定，即n!。这个要求在第一行就说明了。而函数确实必须只生成不同的排列。这就是第二个要求所说的（正如jlouis所指出的那样）。 - CromTheDestroyer

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

基于洗牌算法，但我们每次仅考虑数字的最低位来决定取哪个元素，而不是随机数。或者可以将其视为将数字转换为任意进制的问题，只是每增加一位，基数名称就会缩小。

- Winston Ewert

---

迭代。太好了！我试图像你一样迭代地完成它，但是失败得很惨。我错过了pop调用。 - CromTheDestroyer

这肯定不是真正的O(n)时间，因为pop不是O(1)时间，对吧？ - Reid Barton

Answer 2

你可以使用 factoradics 吗？ 你可以通过这篇MSDN文章找到一个插图。

更新：我编写了一个扩展MSDN算法，可以找到取r个物品的n个元素的第i个排列，即使n != r。

- Joshua Ulrich

---

Joshua，我对代码进行了一些小的优化（使用PHP：http://codepad.org/8ZNZIR1g），我还尝试着做相反的事情（给定某个排列找到其因子进制索引），但没有成功...你不会知道如何做吧？=） - Alix Axel

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)时间内完成。

- aaaaaaaaaaaa

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)

- CromTheDestroyer

Answer 5

有n!种排列方式。第一个字符可以从L中选择n种方式。每个选择会留下(n-1)!种排列方式。所以这个想法足够建立一个顺序。一般来说，你会找出自己在哪一部分，选择合适的元素，然后在较小的L上进行递归/循环。

这个方法正确的论证是通过对序列长度进行归纳。（概述）对于长度为1的情况，它是显而易见的。对于长度为n的情况，你可以利用上面的观察将问题分成n个部分，每个部分都涉及到一个长度为(n-1)的L'。根据归纳假设，所有的L都被正确构造（并且在线性时间内）。然后很明显我们可以使用归纳假设来构造长度为n的解决方案。

- I GIVE CRAP ANSWERS