next_permutation（順列全列挙）

// next_permutation の実装
function nextPermutation(arr) {
    const n = arr.length;
    if (n <= 1) return false;
    
    // ステップ1: 右から最初の昇順位置（ピボット）を見つける
    let i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) {
        i--;
    }
    
    // 最後の順列（降順）の場合
    if (i < 0) {
        arr.reverse(); // 最初の順列に戻す
        return false;
    }
    
    // ステップ2: ピボットより大きい最小の要素を見つける
    let j = n - 1;
    while (arr[j] <= arr[i]) {
        j--;
    }
    
    // ステップ3: ピボットと交換相手を交換
    [arr[i], arr[j]] = [arr[j], arr[i]];
    
    // ステップ4: ピボット以降を昇順に並び替え（反転）
    reverse(arr, i + 1, n - 1);
    
    return true;
}

function reverse(arr, left, right) {
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

// 全順列の生成
function allPermutations(arr) {
    const result = [];
    const copy = [...arr].sort((a, b) => a - b); // 昇順に並び替え
    
    do {
        result.push([...copy]);
    } while (nextPermutation(copy));
    
    return result;
}

// k番目の順列を直接計算
function kthPermutation(n, k) {
    const result = [];
    const nums = Array.from({length: n}, (_, i) => i + 1);
    const factorial = [1];
    
    // 階乗を事前計算
    for (let i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }
    
    k--; // 0-indexed に変換
    
    for (let i = n; i > 0; i--) {
        const index = Math.floor(k / factorial[i - 1]);
        result.push(nums[index]);
        nums.splice(index, 1);
        k %= factorial[i - 1];
    }
    
    return result;
}

// 使用例
const arr = [1, 2, 3];
console.log("初期:", arr);

while (nextPermutation(arr)) {
    console.log("次の順列:", [...arr]);
}

console.log(allPermutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

console.log(kthPermutation(4, 9)); // [2, 3, 1, 4]