count number of partitions of a set with n elements into k subsets

  • A+
Category:Languages

This program is for count number of partitions of a set with n elements into k subsets I am confusing here return k*countP(n-1, k) + countP(n-1, k-1); can some one explain what is happening here? why we are multiplying with k?

NOTE->I know this is not the best way to calculate number of partitions that would be DP

// A C++ program to count number of partitions  // of a set with n elements into k subsets  #include<iostream>  using namespace std;   // Returns count of different partitions of n  // elements in k subsets  int countP(int n, int k)  {      // Base cases      if (n == 0 || k == 0 || k > n)          return 0;      if (k == 1 || k == n)          return 1;       // S(n+1, k) = k*S(n, k) + S(n, k-1)      return k*countP(n-1, k) + countP(n-1, k-1);  }   // Driver program  int main()  {      cout << countP(3, 2);      return 0;  }  

 


What you mentioned is the Stirling numbers of the second kind which enumerates the number of ways to partition a set of n objects into k non-empty subsets and denoted by count number of partitions of a set with n elements into k subsets or count number of partitions of a set with n elements into k subsets.

Its recursive relation is:

count number of partitions of a set with n elements into k subsets

for k > 0 with initial conditions:

count number of partitions of a set with n elements into k subsets

.

Calculating it using dynamic programming is more faster than recursive approach:

int secondKindStirlingNumber(int n, int k) {      int sf[n + 1][n + 1];     for (int i = 0; i < k; i++) {         sf[i][i] = 1;     }     for (int i = 1; i < n + 1; i++) {         for (int j = 1; j < k + 1; j++) {             sf[i][j] = j * sf[i - 1][j] + sf[i - 1][j - 1];         }     }     return sf[n][k]; } 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: