BumbleBee's blog

DP + Combinatorics
By BumbleBee, history, 8 years ago, In English

Suppose, I have N distinct integers. I have to make M non-empty sets using these integers. An integer may not present in any of the sets and an integer can present in only one of the M sets. I have to print all possible ways to make M sets using these N integers.

For example, if I have N = 3 integers which are 1, 2 and 3, then there are 6 possible ways to make M = 2 sets:

1. {1} {2}

2. {1} {3}

3. {2} {3}

4. {1,2} {3}

5. {1,3} {2}

6. {1} {2,3}

How can I find out the number of ways to make M sets using N distinct integers according to the rule given above? What is the most efficient way to print all the possible ways?

I tried to solve this problem using dynamic programming, but I am having trouble to define DP states.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
8 years ago, hide # |
← Rev. 12  
Vote: I like it -10 Vote: I do not like it

Dear BumbleBee,

It seems that an iterative expression can be derived for S(i) defined as the number of non-empty subsets of size i in the N-item set partitioning problem, where i belongs to the interval [ 1, K + 1 ], K = N - M, S(i) belongs to the interval [ 0, N / i ], S(1) + S(2) + .... + S(P) = M, S(1) + 2 S(2) + 3 S(3) + .... + P S(P) = N, and P that belongs to the interval [ 1, M ] is the number of different sizes of the non-empty subsets.

For example, S(1) <= M and N - S(1) >= 2 [ M - S(1) ]. Therefore, N - 2 K <= S(1) <= M. Similarly, S(2) <= M - S(1) and N - S(1) - 2 S(2) >= 3 [ M - S(1) - S(2) ]. Therefore, 2 N - 3 K - 2 S(1) <= S(2) <= M - S(1). Likewise, S(3) <= M - S(1) - S(2) and N - S(1) - 2 S(2) - 3 S(3) >= 4 [ M - S(1) - S(2) - S(3) ]. Therefore, 3 N - 4 K - 3 S(1) - 2 S(2) <= S(3) <= M - S(1) - S(2). Next, 4 N - 5 K - 4 S(1) - 3 S(2) - 2 S(3) <= S(4) <= M - S(1) - S(2) - S(3), and so on.

These examples for i = 1, 2, 3, and 4can be generalized to T(i) <= S(i) <= U(i), where T(i) and U(i) can be expressed as follows. Let V(0) = W(0) = 0, V(i) = V(i-1) + S(i) and W(i) = W(i-1) + i S(i). It follows that V(P) = M and W(P) = N. It also follows that T(1) = M - K and U(1) = M, and that U(i) = M - V(i) and T(i) = T(i-1) + U(i) - S(i) for i > 1.

The number of possible choices for a particular value of S(1) is the combinatorial coefficient C( N - W(0), S(1) ), for S(2) is C( N - W(1), S(2) ), for S(3) is C( N - W(2), S(3) ), and so on. It follows that the number of choices for a particular value of S(i) is C( N - W(i-1), S(i) ).

Hope that this partial problem analysis helps.

Best wishes,

→ Reply
»
8 years ago, hide # |
← Rev. 3  
Vote: I like it +5 Vote: I do not like it

dp[i][j] = number of ways to split i distinct numbers in j non empty-sets

3 cases:

  1. take number i, create new set

  2. take number i, add to some existing set

  3. disgard number i

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it 0 Vote: I do not like it

    I tried to implement your idea in this way:

    #include <bits/stdc++.h>
using namespace std;
int arr[]={1,2,3};  // n integers
vector <int> v[12]; // m sets
void f(int i,int j,int n,int m)
{
    if(j==m) return;
    if(i==n){
        for(int a=0;a<m;a++){
            if(v[a].empty()) return;  //no sets should be empty
        }
        for(int a=0;a<m;a++){  //printing all the sets
            cout<< "{";
            int l=v[a].size();
            for(int b=0;b<l;b++){
                if(b>0) cout<< ",";
                cout<< v[a][b];
            }
            cout<< "} ";
        }
        cout<<endl;
        return;
    }
    for(int a=0;a<=j;a++){      //inserting ith integer in one of the existing set
        v[a].push_back(arr[i]);
        f(i+1,j,n,m);
        v[a].pop_back();
    }
    v[j+1].push_back(arr[i]);   //creating a new set with ith integer
    f(i+1,j+1,n,m);
    v[j+1].pop_back();
    f(i+1,j,n,m);        //disgard ith integer
}
int main()
{
    f(0,0,3,2);
    return 0;
}

    OUTPUT:

    {1,2} {3}

    {1,3} {2}

    {1} {2,3}

    {1} {2}

    {1} {3}

    {2,3} {1}

    {2} {1,3}

    {2} {1}

    {3} {1,2}

    {3} {1}

    {2} {3}

    {3} {2}

    Each combination has appeared twice in the output. How to prevent this?

    → Reply
»
8 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

The answer is :

, where S(i, j) are Stirling number of the second kind.

→ Reply