วิธีคำนวณ Combination และ Permutation ใน C++

ภาพรวม

Combination (การจัดหมู่) และ Permutation (การเรียงสับเปลี่ยน) เป็นส่วนของ Combinatorics ความแตกต่างคือ Permutation สนใจลำดับ ส่วน Combination ไม่สนใจลำดับ

สูตรคณิตศาสตร์

โค้ดตัวอย่าง (ใช้ Factorial แบบ Recursive)

#include <iostream>
using namespace std;

long long fact(int n) {
    if (n == 0 || n == 1) return 1;
    return n * fact(n - 1);
}

int main() {
    int n, r;
    cout << "Enter n: ";
    cin >> n;
    cout << "Enter r: ";
    cin >> r;
    
    if (r > n || r < 0) {
        cout << "Invalid input: r must be between 0 and n";
        return 1;
    }
    
    long long combination = fact(n) / (fact(r) * fact(n - r));
    long long permutation = fact(n) / fact(n - r);
    
    cout << "\nCombination (nCr): " << combination;
    cout << "\nPermutation (nPr): " << permutation;
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter n: 5
Enter r: 3
Combination (nCr): 10
Permutation (nPr): 60

ปัญหา Overflow และการแก้ไข

Factorial เติบโตเร็วมาก 13! = 6,227,020,800 (เกิน 32-bit int) 21! เกิน 64-bit long long

วิธีแก้: คำนวณโดยไม่ต้องหา Factorial เต็ม

// nCr = n*(n-1)*...*(n-r+1) / r!
long long nCr(int n, int r) {
    if (r > n - r) r = n - r;  // ใช้ค่าที่น้อยกว่า
    long long result = 1;
    for (int i = 1; i <= r; i++) {
        result = result * (n - r + i) / i;  // หารทีละขั้นป้องกัน overflow
    }
    return result;
}

// nPr = n*(n-1)*...*(n-r+1)
long long nPr(int n, int r) {
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result *= (n - i);
    }
    return result;
}

การใช้งานใน C++17+

C++17 เพิ่ม std::gcd แต่ยังไม่มี nCr/nPr built-in ต้องเขียนเองหรือใช้ Boost:

// Boost
#include <boost/math/special_functions/binomial.hpp>
double comb = boost::math::binomial_coefficient<double>(n, r);

สรุป