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 >>> kth_permutation(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
(k, n)
| 1 | def kth_permutation(k, n): |
| 2 | """ |
| 3 | Finds k'th lexicographic permutation (in increasing order) of |
| 4 | 0,1,2,...n-1 in O(n^2) time. |
| 5 | |
| 6 | Examples: |
| 7 | First permutation is always 0,1,2,...n |
| 8 | >>> kth_permutation(0,5) |
| 9 | [0, 1, 2, 3, 4] |
| 10 | |
| 11 | The order of permutation of 0,1,2,3 is [0,1,2,3], [0,1,3,2], [0,2,1,3], |
| 12 | [0,2,3,1], [0,3,1,2], [0,3,2,1], [1,0,2,3], [1,0,3,2], [1,2,0,3], |
| 13 | [1,2,3,0], [1,3,0,2] |
| 14 | >>> kth_permutation(10,4) |
| 15 | [1, 3, 0, 2] |
| 16 | """ |
| 17 | # Factorails from 1! to (n-1)! |
| 18 | factorials = [1] |
| 19 | for i in range(2, n): |
| 20 | factorials.append(factorials[-1] * i) |
| 21 | assert 0 <= k < factorials[-1] * n, "k out of bounds" |
| 22 | |
| 23 | permutation = [] |
| 24 | elements = list(range(n)) |
| 25 | |
| 26 | # Find permutation |
| 27 | while factorials: |
| 28 | factorial = factorials.pop() |
| 29 | number, k = divmod(k, factorial) |
| 30 | permutation.append(elements[number]) |
| 31 | elements.remove(elements[number]) |
| 32 | permutation.append(elements[0]) |
| 33 | |
| 34 | return permutation |
| 35 | |
| 36 | |
| 37 | if __name__ == "__main__": |