World's most popular travel blog for travel bloggers.

Exhaustive list of ways to distribute n objects to k sets

, , No Comments
Problem Detail: 

I am working on a research paper and we are developing a brute force algorithm to examine another clustering technique.

In this brute force algorithm we test every possible clustering example and see what natural clusters occur.

The problem comes from the assignment of every possible clustering. If give each value a cluster sequentially the complexity is much higher than necessary and results in many overlaps.

Sequential Example: 5 objects into 3 clusters 11111, 11112, 11113, 11114, 11115, 11121, etc. . .

But 11112 and 11113 are effectively the same. The complexity above is O(k^n) where k is the number of clusters and n is the number of objects. This makes for a terrible time afterwards because duplicates will not be fun to work with and parse. Looking at natural clusters becomes easier with more points as well, and in a simple example, assigning 20 to 5 results in 3,200,000 mostly duplicate clusterings.

If we look at this using combinatorics then we can assign n objects to k groups in (n + k - 1) C (k - 1) ways. This results in 20 objects to 5 clusters having only 10626 different combinations.

Is there any way already made to exhaustively produce these arrangements in this way to eliminate the duplicates?

Asked By : Christopher Bell II
Answered By : Yuval Filmus

The objects you are interested in enumerating are counted by Stirling numbers of the second kind. In particular, $\genfrac{\{}{\}}{0pt}{}{n}{k}$ is the number of ways to partition a set of size $n$ into $k$ non-empty parts. The Stirling numbers satisfy the recurrence $$ \genfrac{\{}{\}}{0pt}{}{n+1}{k} = k\genfrac{\{}{\}}{0pt}{}{n}{k} + \genfrac{\{}{\}}{0pt}{}{n}{k-1}. $$ Indeed, either element $n+1$ is in a partition of its own, or it joins one of the other $k$ parts. The initial conditions are $\genfrac{\{}{\}}{0pt}{}{0}{0} = 1$ and $\genfrac{\{}{\}}{0pt}{}{0}{n} = \genfrac{\{}{\}}{0pt}{}{n}{0} = 0$ for $n > 0$. In other words, if $n = k = 0$ then there is a unique solution (the trivial solution), and if $n = 0$ or $k = 0$ otherwise then there are no solutions.

You can use this recurrence to recursively generate all partitions you are after.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55445

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback