นับจำนวนวิธีแบ่งเซตเป็น k สับเซตด้วย C++

ได้รับตัวเลขสองจำนวน e และ p เป้าหมายคือนับจำนวนวิธีที่เราสามารถแบ่ง e สมาชิกของเซตออกเป็น p ส่วน/สับเซตได้

ตัวอย่าง

Input

e=4 p=2

Output

Count of number of ways to partition a set into k subsets are: 7

Explanation

If elements are: a b c d then ways to divide them into 2 partitions are: (a,b,c)-(d), (a,b)-(c,d), (a,b,c)-(d), (a)-(b,c,d), (a,c)-(b,d), (a,c,d)-(b), (a,b,d)-(c). Total 7 ways.

Input

e=2 p=2

Output

Count of number of ways to partition a set into k subsets are: 1

Explanation

If elements are: a b then ways to divide them into 2 partitions are: (a)-(b). Total 1 way only.

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้ Dynamic Programming การคำนวณที่ใช้ในคำตอบจะเป็นแบบเรียกซ้ำ (recursive) ถ้าเราแบ่งสมาชิกเป็น p ส่วน:

• ถ้า e-1 สมาชิกแบ่งเป็น p ส่วนได้ ways(e-1,p) วิธี แล้วเราสามารถใส่สมาชิกปัจจุบันเข้าไปในหนึ่งใน p ส่วนนี้ได้ p * ways(e-1,p) วิธี
• ถ้า e-1 สมาชิกแบ่งเป็น p-1 ส่วนได้ ways(e-1,p-1) วิธี แล้วใส่ 1 สมาชิกในส่วนแยกอีก 1 ส่วน จะได้ 1 * ways(e-1,p-1) รวมจะได้ p*ways(e-1,p) + ways(e-1,p-1) วิธีนี้จะกลายเป็น recursive

จะมีการคำนวณซ้ำเกิดขึ้น เพื่อป้องกันเรื่องนี้จึงใช้ Dynamic Programming

• รับตัวแปร elements และ partitions เป็นอินพุต
• ฟังก์ชัน partition_k(int elements, int partition) คืนค่าจำนวนวิธีแบ่งเซตเป็น k สับเซต
• สร้างอาร์เรย์ 2 มิติ arr[elements + 1][partition + 1] เก็บค่า ways(e,p) ไว้ที่ arr[e][p]
• ลูป from i=0 ถึง elements ตั้ง arr[i][0] = 0 (จำนวนส่วนเป็น 0 แล้ว ways(i,0)=0)
• ลูป from j=0 ถึง partitions ตั้ง arr[0][j] = 0 (จำนวนสมาชิกเป็น 0 แล้ว ways(0,j)=0)
• วนลูป i=1 ถึง elements และ j=1 ถึง i เติมค่าที่เหลือ
• สำหรับสมาชิกเดียว ways=1 หรือแบ่ง x สมาชิกเป็น x ส่วน มีแค่ 1 วิธี ตั้ง arr[i][j] = 1 ถ้า i==j หรือ j==1
• มิฉะนั้น temp_1 = arr[i-1][j-1], temp_2 = arr[i-1][j] และ arr[i][j] = j * temp_2 + temp_1
• เมื่อลูปจบ arr[elements][partition] จะมีจำนวนวิธีทั้งหมด
• คืนค่า arr[elements][partition] เป็นผลลัพธ์

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int partition_k(int elements, int partition){
    int arr[elements + 1][partition + 1];
    for(int i = 0; i <= elements; i++){
        arr[i][0] = 0;
    }
    for(int j = 0; j <= partition; j++){
        arr[0][j] = 0;
    }
    for(int i = 1; i <= elements; i++){
        for (int j = 1; j <= i; j++){
            if (j == 1 || i == j)
            { arr[i][j] = 1; }
            else{
                int temp_1 = arr[i-1][j-1];
                int temp_2 = arr[i-1][j];
                arr[i][j] = j * temp_2 + temp_1;
            }
        }
    }
    return arr[elements][partition];
}

int main(){
    int elements = 4;
    int partition = 2;
    cout << "Count of number of ways to partition a set into k subsets are: " << partition_k(elements, partition);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of number of ways to partition a set into k subsets are: 7