Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
505 views
in Technique[技术] by (71.8m points)

python - i-th element of k-th permutation

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

You probably cannot get the i'th digit of the k'th permutation of n elements in O(n) time or space, because representing the number k itself requires O(log(n!)) = O(n log n) bits, and any manipulations with it have corresponding time complexity.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...