1

I need a little bit of algorithmic help to improve the performance of an analysis.

The Problem:

given a set of N many elements X[0], ..., X[N-1]: I need all possible ways of dividing those N elements into M many distinct subsets each with N / M many elements (let us assume N can always be divided by M).

When I refer to a set I mean the mathematic definition of a set. The ordering of elements is of no importance. For example {A, B} is equal to {B, A}.

Example:

N = 6
M = 2
Input := {X0, X1, X2, X3, X4, X5}
Output := 
{X0, X1}, {X2, X3}, {X4, X5}
{X2, X1}, {X0, X3}, {X4, X5}
{X3, X1}, {X2, X0}, {X4, X5}
{X4, X1}, {X2, X3}, {X0, X5}
{X5, X1}, {X2, X3}, {X4, X0}
...

A trivial solution to this problem is to iterate over all permutations of the initial set, for example with Heaps Algorithm, and then divide into equally sized chunks. This however creates more combinations than are needed since changing the order of elements within a set makes no difference to the set but still constitutes a different permutation if the set is represented as an array in a naive implementation of Heaps Algorithm.

What I would like to know is if there is a known algorithm for this problem or for a similar problem. Or perhaps if the approach via the permutation algorithm + filtering is as good as it gets.

If more information is required please ask.

Thank you very much.

DudeDoesThings
  • 729
  • 3
  • 13
  • Do you need to just count them or you need to actually know all possible solutions? – juvian Aug 27 '18 at 14:13
  • I need to score each possible combination and select the one with the best score. I have done some more thinking and calculations. I believe the number of distinct subsets of size M for N many elements is the binomial coefficient of N over M. For the example I gave above this would result in 6 over 2 times 4 over 2 possible == 90 combinations. But my math might be wrong on this one. – DudeDoesThings Aug 27 '18 at 15:13
  • How is the score determined? – juvian Aug 27 '18 at 15:20
  • As for the amount of ways, [here is the formula](https://math.stackexchange.com/questions/1471101/number-of-partitions-of-a-set-into-subsets-of-cardinality-k) – juvian Aug 27 '18 at 15:26
  • Is the order of subsets in a subduvision important? I.e. is {{1,2},{3,4}} the same as {{3,4},{1,2}}? – n. m. could be an AI Aug 27 '18 at 17:04
  • The order of the subdivisions is not important to me. The scoring is a rather complicated computation taking all the pairings in the combination into account as well as the individual properties of the elements. It is not really important to the base problem though. – DudeDoesThings Aug 27 '18 at 17:41
  • Use a recursive algorithm; keep the first element in the first subset to avoid duplicates; only use elements in order to avoid permutations of the same subset; for each subset S1, recurse and do the same with the left-over elements, i.e. keep the first element in subset S2 to avoid duplicates, and so on... (I think I've written an answer about this; I'll see if I can find it) – m69's been on strike for years Aug 27 '18 at 17:51

0 Answers0