Is there a fast algorithm to compute the i-th element (0 <= i < n)
of the k-th permutation (0 <= k < n!)
of the sequence 0..n-1?
Any order of the permutations may be chosen, it does not have to be lexicographical. There are algorithms that construct the k
-th permutation in O(n)
(see below). But here the complete permutation is not needed, just its i
-th element. Are there algorithms that can do better than O(n)
?
Is there an algorithm that has a space complexity less than O(n)?
There are algorithms that construct the k
-th permutation by working on an array of size n
(see below), but the space requirements might be undesirable for large n
. Is there an algorithm that needs less space, especially when only the i
-th element is needed?
Algorithm that constructs the k
-th permutation of the sequence 0..n-1
with a time and space complexity of O(n)
:
def kth_permutation(n, k):
p = range(n)
while n > 0:
p[n - 1], p[k % n] = p[k % n], p[n - 1]
k /= n
n -= 1
return p
Source: http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…