K-th Alternating Permutation
HardCombinatorics · Atlassian
A permutation of the integers 1 through n is alternating if every pair of neighbouring values has one odd and one even number. For example [3, 2, 1, 4] is alternating, while [1, 3, 2, 4] is not because 1 and 3 are both odd.
List all alternating permutations of 1..n in lexicographic (dictionary) order. Return the k-th one in that list, counting from 1. If there are fewer than k alternating permutations, return an empty list.
Example 1
- Input:
- n = 4, k = 5
- Output:
- [3, 2, 1, 4]
- Explanation
- The 8 alternating permutations of
1..4in order are[1,2,3,4],[1,4,3,2],[2,1,4,3],[2,3,4,1],[3,2,1,4],[3,4,1,2],[4,1,2,3],[4,3,2,1]. The fifth is[3, 2, 1, 4].
Example 2
- Input:
- n = 5, k = 7
- Output:
- [3, 4, 1, 2, 5]
- Explanation
- With three odd and two even values the permutation must start odd, and each starting value leaves
2! * 2! = 4completions. Permutations 1-4 start with 1, so the 7th is the 3rd starting with 3. Those starting3, 2are the 5th and 6th, so the answer is the first starting3, 4:[3, 4, 1, 2, 5].
Example 3
- Input:
- n = 3, k = 3
- Output:
- []
- Explanation
- Only
[1, 2, 3]and[3, 2, 1]alternate, so there is no third one.
Constraints
1 <= n <= 1001 <= k <= 10^15