Pattern Guide
Permutation Patterns
"Next permutation, cycle decomposition, inversions, k-th permutation in O(n)."
Permutation problems cover: generating the next/previous permutation in O(n), finding the k-th permutation in factorial number system O(n²), decomposing a permutation into cycles, counting inversions, and detecting permutation parity. These techniques appear in scheduling, anagram problems, and combinatorics. The factorial number system converts a rank k to a specific permutation directly.
Problems you can solve with this pattern
5 problems · click any to start solving
// Next permutation in O(n)
function nextPermutation(nums) {
const n = nums.length;
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
let j = n - 1;
while (nums[j] <= nums[i]) j--;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
// Reverse suffix [i+1, n-1]
let l = i + 1, r = n - 1;
while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
}
// K-th permutation (1-indexed, 0-indexed internally) in O(n²)
function kthPermutation(n, k) {
const digits = Array.from({length: n}, (_, i) => i + 1);
const fact = new Array(n).fill(1);
for (let i = 1; i < n; i++) fact[i] = fact[i - 1] * i;
k--; // convert to 0-indexed
const result = [];
for (let i = n - 1; i >= 0; i--) {
const idx = Math.floor(k / fact[i]);
result.push(digits[idx]);
digits.splice(idx, 1);
k %= fact[i];
}
return result.join('');
}
// Cycle decomposition: permutation as product of disjoint cycles
function getCycles(perm) { // 0-indexed
const visited = new Array(perm.length).fill(false), cycles = [];
for (let i = 0; i < perm.length; i++) {
if (visited[i]) continue;
const cycle = [];
let j = i;
while (!visited[j]) { visited[j] = true; cycle.push(j); j = perm[j]; }
cycles.push(cycle);
}
return cycles;
}Next permutation algorithm: (1) find rightmost position i where nums[i] < nums[i+1], (2) find rightmost j > i where nums[j] > nums[i], (3) swap nums[i] and nums[j], (4) reverse suffix starting at i+1. This gives the lexicographically next permutation in O(n). For k-th permutation: convert k to factorial number system — repeatedly extract digit by dividing by (n-1)!, (n-2)!, etc.
// Next permutation in O(n)
function nextPermutation(nums) {
const n = nums.length;
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
let j = n - 1;
while (nums[j] <= nums[i]) j--;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
// Reverse suffix [i+1, n-1]
let l = i + 1, r = n - 1;
while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
}
// K-th permutation (1-indexed, 0-indexed internally) in O(n²)
function kthPermutation(n, k) {
const digits = Array.from({length: n}, (_, i) => i + 1);
const fact = new Array(n).fill(1);
for (let i = 1; i < n; i++) fact[i] = fact[i - 1] * i;
k--; // convert to 0-indexed
const result = [];
for (let i = n - 1; i >= 0; i--) {
const idx = Math.floor(k / fact[i]);
result.push(digits[idx]);
digits.splice(idx, 1);
k %= fact[i];
}
return result.join('');
}
// Cycle decomposition: permutation as product of disjoint cycles
function getCycles(perm) { // 0-indexed
const visited = new Array(perm.length).fill(false), cycles = [];
for (let i = 0; i < perm.length; i++) {
if (visited[i]) continue;
const cycle = [];
let j = i;
while (!visited[j]) { visited[j] = true; cycle.push(j); j = perm[j]; }
cycles.push(cycle);
}
return cycles;
}- Next permutation: O(n), in-place
- K-th permutation: O(n²) using factorial number system
- Permutation parity: even/odd based on number of inversions
- Minimum swaps to sort: n - (number of cycles)
- Cycle decomposition: each element visited exactly once
Factorial number system: n digits represent a unique permutation. Digit i (0-indexed from right) ranges from 0 to i. Convert k to this system to find the k-th permutation directly without generating all previous ones.