nCk組み合わせ計算

// 最適化されたnCk組み合わせ計算
function combinationOptimized(n, k) {
    // 対称性を利用した効率化
    if (k > n - k) k = n - k;
    
    if (k === 0) return 1;
    if (k === 1) return n;
    
    let result = 1;
    for (let i = 0; i < k; i++) {
        result = (result * (n - i)) / (i + 1);
    }
    return result;
}

// 階乗による基本計算
function combinationFactorial(n, k) {
    if (k > n || k < 0) return 0;
    
    function factorial(num) {
        if (num <= 1) return 1;
        let result = 1;
        for (let i = 2; i <= num; i++) {
            result *= i;
        }
        return result;
    }
    
    return factorial(n) / (factorial(k) * factorial(n - k));
}

// パスカルの三角形による動的計画法
function combinationPascal(n, k) {
    if (k > n - k) k = n - k;  // 効率化
    
    let prev = new Array(k + 1).fill(0);
    let curr = new Array(k + 1).fill(0);
    
    prev[0] = 1;
    
    for (let i = 1; i <= n; i++) {
        curr[0] = 1;
        for (let j = 1; j <= Math.min(i, k); j++) {
            curr[j] = prev[j - 1] + (prev[j] || 0);
        }
        [prev, curr] = [curr, prev];
        curr.fill(0);
    }
    
    return prev[k];
}

// 安全な逐次計算
function combinationSafe(n, k) {
    if (k === 0 || k === n) return 1;
    if (k > n - k) k = n - k;  // 効率化
    
    let result = 1;
    for (let i = 0; i < k; i++) {
        // 乗算と除算を適切な順序で実行
        result = Math.floor((result * (n - i)) / (i + 1));
    }
    return result;
}

// 使用例
console.log(combinationOptimized(5, 2));    // 10
console.log(combinationFactorial(6, 3));    // 20
console.log(combinationPascal(8, 2));       // 28
console.log(combinationSafe(10, 5));        // 252

// 効率性の比較
function compareMethodsEfficiency(n, k) {
    console.log(`C(${n},${k})の計算方法比較:`);
    
    // 最適化法
    console.time('最適化法');
    const optimized = combinationOptimized(n, k);
    console.timeEnd('最適化法');
    
    // 階乗法（小さなnのみ）
    if (n <= 15) {
        console.time('階乗法');
        const factorial = combinationFactorial(n, k);
        console.timeEnd('階乗法');
    }
    
    // パスカル法
    console.time('パスカル法');
    const pascal = combinationPascal(n, k);
    console.timeEnd('パスカル法');
    
    console.log(`結果: ${optimized}`);
    console.log(`計算量: O(min(${k}, ${n-k}))`);
}

compareMethodsEfficiency(15, 7);

// 実用的な応用例
class CombinationCalculator {
    // メモ化による高速化
    constructor() {
        this.memo = new Map();
    }
    
    calculate(n, k) {
        const key = `${n},${k}`;
        if (this.memo.has(key)) {
            return this.memo.get(key);
        }
        
        const result = combinationOptimized(n, k);
        this.memo.set(key, result);
        return result;
    }
    
    // 確率計算への応用
    probabilityOfExact(n, k, p) {
        // 二項分布: P(X = k) = C(n,k) * p^k * (1-p)^(n-k)
        const combination = this.calculate(n, k);
        return combination * Math.pow(p, k) * Math.pow(1 - p, n - k);
    }
    
    // サンプリング計算
    samplingCombinations(population, sampleSize) {
        return this.calculate(population, sampleSize);
    }
}

// 電卓インスタンス
const calc = new CombinationCalculator();

// 確率論での使用例
console.log('10回コイン投げで5回表が出る確率:');
console.log(calc.probabilityOfExact(10, 5, 0.5));  // ≈ 0.246

// サンプリングでの使用例
console.log('100人から10人のサンプルを選ぶ方法:');
console.log(calc.samplingCombinations(100, 10));   // 4.26×10^13

// 大きな数値での安全な計算
function largeCombinationSafe(n, k) {
    if (k > n - k) k = n - k;
    
    // 対数を使用した数値安定化
    let logResult = 0;
    for (let i = 0; i < k; i++) {
        logResult += Math.log(n - i) - Math.log(i + 1);
    }
    
    return Math.round(Math.exp(logResult));
}

console.log('大きな数値: C(50, 25) ≈', largeCombinationSafe(50, 25));