Permutation Patterns

// 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;
}