Computer >> Máy Tính >  >> Lập trình >> C ++

Đếm số cách để phân vùng một tập hợp thành k tập hợp con trong C ++

Cho hai số e và p. Mục đích 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 

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

Giải thích 

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.

Đầu vào 

e=2 p=2

Đầu ra 

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

Giải thích 

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ sử dụng cách tiếp cận lập trình động. Các phép tính được sử dụng trong giải pháp sẽ luôn luôn là đệ quy. Nếu chúng ta chia các phần tử thành các phần p thì -

  • Nếu e-1 phần tử có thể được chia thành p phân hoạch theo cách (e-1, p). Sau đó, chúng ta có thể đặt phần tử hiện tại vào một trong các phân vùng p này theo cách p * (e-1, p).

  • Nếu các phần tử e − 1 được chia thành các phân hoạch p − 1 theo các cách (e − 1, p − 1) thì khi đưa 1 phần tử vào 1 phân hoạch riêng biệt đó sẽ có 1 * cách (e − 1, p − 1). Tổng số cách sẽ làp * cách (e − 1, p) + cách (e − 1, p − 1). Phương thức này sẽ trở thành đệ quy -

Đếm số cách để phân vùng một tập hợp thành k tập hợp con trong C ++

Như được hiển thị ở trên các tính toán trùng lặp sẽ được thực hiện. Để tránh điều này, chúng tôi sẽ sử dụng phương pháp lập trình adynamic.

  • Lấy các biến, phần tử và phân vùng làm đầu vào.

  • Hàm partition_k (phần tử int, phân vùng int) nhận cả hai biến và trả về số cách phân chia một tập hợp thành k tập hợp con.

  • Lấy mảng 2D arr [phần tử + 1] [phân vùng + 1] để lưu trữ giá trị của các cách (e, p) trong arr [e] [p].

  • Sử dụng vòng lặp for từ i =0 đến i =phần tử, đặt arr [i] [0] =0 vì số lượng tiêu chí là 0 thì cách (i, 0) =0.

  • Một lần nữa sử dụng vòng lặp for từ j =0 đến i =phân vùng, đặt arr [0] [j] =0 vì số phần tử là 0 sau đó cách (0, i) =0.

  • Bây giờ duyệt arr [] [] bằng cách sử dụng hai vòng lặp for từ i =1 đến i <=phần tử 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ử duy nhất, chỉ có 1 cách =1 hoặc để chia x phần tử thành x phân vùng thì chỉ có 1 cách. Vì vậy, hãy đặt arr [i] [j] =1 trong trường hợp i ==j hoặc j ==1.

  • Nếu không, hãy đặ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 tất cả các vòng lặp, chúng ta sẽ có arr [phần tử] [phân vùng] là tổng số cách.

  • Kết quả là trả về arr [phần tử] [phân vùng].

Ví dụ 

#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][partition] = 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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau - 

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