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.

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 4`

can 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,

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

3 cases:

take number i, create new set

take number i, add to some existing set

disgard number i

I tried to implement your idea in this way:

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?

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

The answer is :

, where

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