CODEWITHSUNDEEP
mathcombinationscounting
cubesnyc
cubesnyc

Reputation: 1545

Combinations with multiple groups

How would you programmatically enumerate all possible unique combinations of a set of numbers into multiple groups?

For example, if I have the set {1,2,3,4,5,6,7,8,9,10} and I want 3 groups of size 3, 3, 2 one possible subset would be { [1, 2, 3], [4, 5, 6], [7, 8] }

this would be equivalent to { [3, 2, 1], [6, 5, 4], [7, 8] } and would be considered a duplicate

whereas { [4, 2, 3], [1, 5, 6], [7, 8] } would be considered a different subset

Obviously I am looking for the most efficient and practical way of doing this. I will be working with a fairly large N so the algorithm needs to be scalable.

Upvotes: 1

Views: 2424

Answers (1)

MvG
MvG

Reputation: 60868

Another way to think of this problem is as permutations of the multiset {1, 1, 1, 2, 2, 2, 3, 3}. If such a permutation p has value i in position j, that would mean that the element j from your original set should be put in partition i.

Using e.g. the C++ template next_permutation you can enumerate these permutations as follows:

int main() {
  int a[] = { 0, 0, 0, 1, 1, 1, 2, 2 };
  do {
    // Here a[j] == i means element j of your set goes in partition i.
    // Do whatever you want to do with the permutations generated this way.
  } while (std::next_permutation(a, a + 8));
}

The result will contain 10!/(3! 3! 2!) = 560 different combinations. A demo run of this code, including output similar to the notation used in your problem statement, is available at ideone. You can look at the source code if you want to know how next_permutation is implemented for gcc, but only do so if the license of your target project allows copying that code.

Upvotes: 1

Related Questions