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?