线性时间常数空间置换发生器

Question

是否有一个生成函数f（i，j，n）在确定性的恒定时间和空间中返回第j个置换的第i个元素（0 < = i < n） 0 < = j < n！）前n个整数？如果是这样，它是如何工作的？如果没有，我可以看到一个disproof？

这个问题是与此相关的一个：Create a random permutation of 1..N in constant space 然而，在这种情况下，我们希望能够产生每排列，这取决于我们的选择j的，不只是一个特定的或任意一个。

它也与此相关：Random access random permutations （事实上，这可能就是这个问题的作者所希望拥有的东西，尽管我不能确定这个问题没有更具体和更具约束性。无论如何，我对并行化并不感兴趣。）

如果可能的话，那么我也想知道如果我们可以消除参数j（因为它的长度是O（n））并且只是产生一个置换无需先将其命名即可随意选择。

如果是不可能的，那么我不知道是否有可能概率（但仍然在确定性线性时间和恒定的空间）产生一个统一选择置换。例如，一种产生均匀选择的序列的方法，该序列恰好也是时间> 1％的置换。

我问这个问题，因为所有的我所知道的方法生成置换或者需要存储的值的范围被明确置换，或者至少存储所有这些迄今已产生的数字。

Answer 1

前段时间我为this problem做了类似的事情。

对您的问题稍作修改后，它会直接生成第j个排列，然后选择其第i个元素。

#!/usr/bin/env python3 

from math import factorial 

def getJthPermutation(initList, j): 
    j -= 1 

    result = "" 
    fac = factorial(len(initList) - 1) 
    for div in range(len(initList) - 1, 0, -1): 
     k = j // fac 
     result += initList[k] 
     del initList[k] 

     j %= fac 

     fac //= div 
    result += initList[0] 

    return result 


def fct(i, j, n): 
    list = [str(k) for k in range(n+1)] 

    permutation = getNPermutation(list[:], j) 

    return permutation[i] 


if __name__ == "__main__": 
    print(fct(3,1000000,9)) 
    print(fct(3,1,9)) 
    print(fct(1,factorial(9), 9)) 

(if you don't have python installed)

意愿仍取决于n，但不能在i也不j复杂性（如果我没有记错的话）。