Generate Alternating Parity Permutations
In many combinatorial problems, generating sequences with specific properties is a core task. For instance, in data validation, cryptographic key generation, or even game design, we might need to produce sequences where adjacent elements follow a particular rule. This problem asks you to generate all unique permutations of a given length, where adjacent elements must strictly alternate in parity (even/odd).
Your task is to implement a function generateAlternatingPermutations that finds all distinct permutations of a specified length k, using numbers from 1 to n (inclusive). The critical constraint is that any two adjacent numbers in a generated permutation must have different parities (one even, one odd).
Specifically, you must:
k.{1, 2, ..., n}.arr[i] and arr[i+1] in a permutation, arr[i] % 2 != arr[i+1] % 2.Function Signature:
function generateAlternatingPermutations(n: number, k: number): number[][];
Input:
n: A positive integer representing the upper bound (inclusive) for the numbers available for permutations. Numbers will be chosen from [1, n].k: A positive integer representing the desired length of each permutation.Output:
number[][]). Each inner array represents a valid permutation satisfying all the given constraints. The order of permutations in the output array does not matter, but the order of elements within each permutation does.k is greater than n, it's impossible to form a permutation with k unique elements from 1 to n. In this case, return an empty array [].1 through n are available for selection. Each number can only be used once within a single permutation.num % 2 === 0, and odd if num % 2 !== 0.Examples
Example 1
Input:
n = 3, k = 2
Output:
[[1,2],[2,1],[2,3],[3,2]]
Note:
For n=3, k=2:
Example 2
Input:
n = 4, k = 3
Output:
[[1,2,3],[1,4,3],[2,1,4],[2,3,4],[3,2,1],[3,4,1],[4,1,2],[4,3,2]]
Note:
All listed permutations satisfy the alternating parity and uniqueness constraints. For example, [1,2,3]: 1(O)-2(E) is valid, 2(E)-3(O) is valid. [1,3,2] would be invalid because 1 and 3 are both odd.
Example 3
Input:
n = 2, k = 3
Output:
[]
Note:
It's impossible to form a permutation of length 3 using unique numbers from 1 to 2. Therefore, an empty array is returned.
Constraints
1 <= k <= n <= 8n and k will always be positive integers.n or k).Loading editor...