Given two integers n and k, we want to generate the k-th lexicographically smallest “alternating permutation” of the numbers 1 through n. An alternating permutation is defined as one in which no two adjacent elements have the same parity (i.e. both odd or both even). If there are fewer than k valid alternating permutations, return an empty list.
For example, for n = 4 the valid alternating permutations in lexicographical 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]
If k = 6 then the answer is [3, 4, 1, 2].
Key Insights
The “alternating” constraint forces the parity pattern of the permutation (i.e. odd-even-odd… or even-odd-even…) once the first element is chosen.
The overall counts of odds and evens in 1 through n are fixed. Let oddTotal = ⎡n/2⎤ and evenTotal = ⎣n/2⎦.
When n is odd the valid pattern is forced (the first element must be the parity with more numbers) while if n is even both starting parities are possible.
Once the parity for a certain position is fixed, the number of completions depends only on the counts of the remaining available odd and even numbers.
The number of completions from a state having rOdd odd numbers and rEven even numbers can be computed as fact(rOdd) * fact(rEven) (using a “capped” multiplication since k can be at most 10^15).
Use a “skip‐count” technique: at each step, iterate over available candidates (in sorted order) that are valid (matching the required parity), count how many completions each selection would yield, and “skip” over candidates if the branch count is smaller than k.
Space and Time Complexity
Time Complexity: O(n · m) where m is the time needed for factorial lookups and the iterations over the available numbers. Here n ≤ 100 and the available candidates in each step are at most n.
Space Complexity: O(n) for storing the lists of available odd and even numbers and the eventual result.
Solution
We first precompute factorials for numbers up to n (capped to avoid overflow beyond k). Notice that the entire permutation’s parity pattern is fixed by the first element. In the first step, if the counts of odd and even numbers are unequal, then only one type of number can start the permutation (e.g. for n odd, oddTotal > evenTotal then the first element must be odd). If they are equal, then both odd and even candidates are allowed.
At each subsequent position, we know exactly which parity is required (the opposite of the previous element), and the number of completions possible from that state is simply fact(remainingOdd)*fact(remainingEven). We iterate over the sorted available candidates for that parity and subtract the branch count until the candidate that “contains” the kth permutation is found.
Data structures used include separate sorted lists for odd and even numbers. The algorithmic approach is backtracking with “skipping” using combinatorial counts; we never generate all permutations but count completions using factorial values.
Code Solutions
# Precompute factorial values with a cap to avoid huge numbers# We cap at INF which is above the maximum possible k.INF =10**18defcompute_factorials(n): fact =[1]*(n +1)for i inrange(1, n+1): fact[i]= fact[i-1]* i
if fact[i]> INF: fact[i]= INF
return fact
defkth_alternating_permutation(n, k):# Precomputations: odd and even counts. oddTotal =(n +1)//2 evenTotal = n //2 fact = compute_factorials(n)# n is at most 100# Prepare the available numbers in sorted order available_odds =[x for x inrange(1, n+1)if x %2==1] available_evens =[x for x inrange(1, n+1)if x %2==0] result =[]# Decide valid candidates for the first position# If counts differ, only one parity can be used to have a valid alternating sequence. first_candidates =[]if oddTotal > evenTotal: first_candidates = available_odds[:]# only odd numbers allowedelif evenTotal > oddTotal: first_candidates = available_evens[:]# only even numbers allowedelse:# if counts are equal, any number (odd or even) is allowed. first_candidates =list(range(1, n+1)) current_odd = oddTotal
current_even = evenTotal
# choose first element by iterating over valid candidates in sorted order. chosen_first =Nonefor candidate in first_candidates:# For candidate selection, determine the branch count.if candidate %2==1:# candidate is odd; if chosen, the remaining odd count becomes current_odd-1 branch_count = fact[current_odd -1]* fact[current_even]else: branch_count = fact[current_even -1]* fact[current_odd]if k > branch_count: k -= branch_count
else:# Candidate found. chosen_first = candidate
result.append(candidate)# Remove candidate from the corresponding available list.if candidate %2==1: available_odds.remove(candidate) current_odd -=1 required_parity =0# next must be evenelse: available_evens.remove(candidate) current_even -=1 required_parity =1# next must be oddbreak# If no first candidate was chosen then kth permutation does not exist.if chosen_first isNone:return[]# For positions 2 through n, the required parity alternates.while current_odd + current_even >0:# candidate list depends on required_parity.if required_parity ==1:# need odd number candidates = available_odds
else:# required_parity == 0, need even number candidates = available_evens
chosen =None# Iterate in sorted order among candidates of the required parity.for cand insorted(candidates):if required_parity ==1: branch_count = fact[current_odd -1]* fact[current_even]if current_odd >0else0else: branch_count = fact[current_even -1]* fact[current_odd]if current_even >0else0if k > branch_count: k -= branch_count
else: chosen = cand
result.append(cand)if required_parity ==1: available_odds.remove(cand) current_odd -=1 required_parity =0# alternate to even nextelse: available_evens.remove(cand) current_even -=1 required_parity =1# alternate to odd nextbreakif chosen isNone:return[]# kth permutation does not exist if candidate not foundreturn result
# Example usage:#print(kth_alternating_permutation(4, 6)) # Expected output: [3, 4, 1, 2]#print(kth_alternating_permutation(3, 2)) # Expected output: [3, 2, 1]#print(kth_alternating_permutation(2, 3)) # Expected output: []