sadman.rizwan's blog

By sadman.rizwan, history, 12 days 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  

»
12 days ago, # |
Rev. 12   Vote: I like it -10 Vote: I do not like it

Dear sadman.rizwan,

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,

»
12 days ago, # |
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

  • »
    »
    11 days ago, # ^ |
    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?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Solved. I had to put a condition while creating a new set with the ith integer. Thanks.

»
12 days ago, # |
  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.