kth lexicographic permutation Algorithm
The kth lexicographic permutation algorithm is a method used to find the kth permutation of a sequence of objects in lexicographically sorted order. This algorithm is particularly useful in combinatorial problems where the number of possible permutations can be extremely large, and a specific permutation needs to be identified without generating all possible permutations. It is often used in solving problems related to permutations and combinations, such as the traveling salesman problem, as well as in cryptography and computer science.
The algorithm works by using factorials and the concept of "lexicographic order" to determine the kth permutation directly. The basic idea is to represent the kth permutation as a sequence of numbers, where each number corresponds to the index of an element in the original sequence. The algorithm starts by calculating factorials of the sequence length and using these factorials to determine the appropriate element at each position. The key to the algorithm is that it does not require the generation of all previous permutations to arrive at the kth one, which makes it highly efficient. Once the sequence of indices is obtained, the corresponding elements can be mapped back to the original sequence to generate the kth permutation. This method can be applied to both numerical and non-numerical sequences, making it a versatile and powerful tool in solving a wide range of problems.
def kthPermutation(k, n):
"""
Finds k'th lexicographic permutation (in increasing order) of
0,1,2,...n-1 in O(n^2) time.
Examples:
First permutation is always 0,1,2,...n
>>> kthPermutation(0,5)
[0, 1, 2, 3, 4]
The order of permutation of 0,1,2,3 is [0,1,2,3], [0,1,3,2], [0,2,1,3],
[0,2,3,1], [0,3,1,2], [0,3,2,1], [1,0,2,3], [1,0,3,2], [1,2,0,3],
[1,2,3,0], [1,3,0,2]
>>> kthPermutation(10,4)
[1, 3, 0, 2]
"""
# Factorails from 1! to (n-1)!
factorials = [1]
for i in range(2, n):
factorials.append(factorials[-1] * i)
assert 0 <= k < factorials[-1] * n, "k out of bounds"
permutation = []
elements = list(range(n))
# Find permutation
while factorials:
factorial = factorials.pop()
number, k = divmod(k, factorial)
permutation.append(elements[number])
elements.remove(elements[number])
permutation.append(elements[0])
return permutation
if __name__ == "__main__":
import doctest
doctest.testmod()
