By sadman.rizwan, history, 7 months ago, ,

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.

•
• +7
•

 » 7 months ago, # | ← Rev. 12 →   -10 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,
 » 7 months ago, # | ← Rev. 3 →   +5 dp[i][j] = number of ways to split i distinct numbers in j non empty-sets3 cases: take number i, create new set take number i, add to some existing set disgard number i
•  » » 7 months ago, # ^ | ← Rev. 4 →   0 I tried to implement your idea in this way: #include using namespace std; int arr[]={1,2,3}; // n integers vector 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;a0) cout<< ","; cout<< v[a][b]; } cout<< "} "; } cout<
•  » » » 7 months ago, # ^ |   0 Solved. I had to put a condition while creating a new set with the ith integer. Thanks.
 » 7 months ago, # |   +16 The answer is :, where S(i, j) are Stirling number of the second kind.