C++ การเรียงสับเปลี่ยน n เลือก r พร้อม k อยู่ด้วยกัน

กำหนด n, r, k ตอนนี้เราต้องหาว่าสามารถเลือก r สิ่งจาก n ได้กี่วิธี โดยที่ k สิ่งเฉพาะต้องอยู่ด้วยกันเสมอ เช่น

Input : n = 8, r = 5, k = 2 Output : 960
Input : n = 6, r = 2, k = 2 Output : 2

เราต้องมีความรู้เล็กน้อยสำหรับปัญหานี้ เพราะโจทย์ถามให้หาการเรียงสับเปลี่ยน (Permutation) ของ n และ r ที่ k สิ่งอยู่ด้วยกัน

วิธีการแก้ปัญหา

เราต้องสร้างสูตรสำหรับคำถามนี้ ซึ่งจะให้คำตอบที่ต้องการ

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

int fact(int n){ 
    if(n <= 1) return 1; 
    return n * fact(n-1); 
} 

int npr(int n, int r){ 
    int pnr = fact(n) / fact(n - r); 
    return pnr; 
} 

int countPermutations(int n, int r, int k){ 
    return fact(k) * (r - k + 1) * npr(n - k, r - k); 
} 

int main(){ 
    int n = 8; 
    int r = 5; 
    int k = 2; 
    cout << countPermutations(n, r, k); 
    return 0; 
}

ผลลัพธ์

960

คำอธิบายโค้ด

ในวิธีนี้ เราพยายามสร้างสูตรคำนวณคำตอบ สูตรที่เราสร้างคือ (k!) * (r - k + 1) * P(n-k, r-k) โดย P(x, y) คือจำนวนการเรียงสับเปลี่ยนเลือก y จาก x ดังนั้นเรานำสูตรมาใช้และคำนวณคำตอบ

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาการหา Permutations of n things taken r at a time with k things together เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์