如何生成排列？

Question

我的问题是:给定一个长度为n的列表L,以及一个整数i,使得0 <= i <n !,如何编写函数perm(L,n)以在O(n)中产生L的第i个排列时间？我所说的ith排列只是在某些实现定义的排序中的第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

基于混洗算法,但我们每次采用数字中最不重要的部分来决定采用哪个元素而不是随机数.或者将其视为转换为某个任意基数的问题,除了基本名称每增加一个数字缩小.