Đếm số cách phân chia tập hợp thành k tập con trong C++

Cho hai số e và p. Mục tiêu là đếm số cách mà chúng ta có thể chia e phần tử của một tập hợp thành p phân vùng/tập con.

Ví dụ

Đầu vào

e=4 p=2

Đầu ra

Số cách phân chia tập hợp thành k tập con là: 7

Giải thích

Nếu các phần tử là: a b c d thì cách chia chúng thành 2 phân vùng là: (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). Tổng 7 cách.

Đầu vào

e=2 p=2

Đầu ra

Số cách phân chia tập hợp thành k tập con là: 1

Giải thích

Nếu các phần tử là: a b thì cách chia chúng thành 2 phân vùng là: (a)-(b). Chỉ có 1 cách duy nhất.

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ sử dụng phương pháp quy hoạch động. Các phép tính dùng trong giải pháp sẽ luôn là đệ quy. Nếu chúng ta chia các phần tử thành p phân vùng thì:

Nếu e-1 phần tử có thể được chia thành p phân vùng theo ways(e-1,p) cách. Khi đó ta có thể đặt phần tử hiện tại vào một trong p phân vùng này theo p*ways(e-1,p) cách.
Nếu e-1 phần tử được chia thành p-1 phân vùng theo ways(e-1,p-1) cách thì việc đặt 1 phần tử vào phân vùng riêng biệt đó sẽ có 1*ways(e-1,p-1) cách. Tổng số cách sẽ là p*ways(e-1,p) + ways(e-1,p-1). Phương pháp này sẽ trở nên đệ quy.

Như hình trên, các phép tính trùng lặp sẽ được thực hiện. Để tránh điều này, chúng ta sẽ sử dụng phương pháp quy hoạch động.

Nhận biến elements và partitions làm đầu vào.
Hàm partition_k(int elements, int partition) nhận cả hai biến và trả về số lượng cách phân chia tập hợp thành k tập con.
Tạo mảng 2D arr[elements + 1][partition + 1] để lưu giá trị của ways(e,p) trong arr[e][p].
Sử dụng vòng lặp for từ i=0 đến i=elements, đặt arr[i][0] = 0 vì số phân vùng là 0 thì ways(i,0)=0.
Lại sử dụng vòng lặp for từ j=0 đến i=partitions, đặt arr[0][j] = 0 vì số phần tử là 0 thì ways(0,i)=0.
Bây giờ duyệt arr[][] bằng hai vòng lặp for từ i=1 đến i<=elements và j=1 đến j<=i và điền các giá trị còn lại.
Đối với một phần tử đơn lẻ, số cách = 1 hoặc chia x phần tử thành x phân vùng chỉ có 1 cách. Vì vậy đặt arr[i][j] = 1 trong trường hợp i==j hoặc j==1.
Ngược lại đặt temp_1 = arr[i-1][j-1] và temp_2 = arr[i-1][j] và cập nhật arr[i][j] = j * temp_2 + temp_1.
Cuối cùng của tất cả vòng lặp, chúng ta sẽ có arr[elements][partition] là tổng số cách.
Trả về arr[elements][partition] làm kết quả.

Ví dụ mã

#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 << "Số cách phân chia tập hợp thành k tập con là: " << partition_k(elements, partition);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách phân chia tập hợp thành k tập con là: 7