0

I am looking for an algorithm that, given an array of elements, for example [1,2,3] will output all possible combinations of groups of these elements. It is trivial to find all possible groups. In this example, all possible groups will be:

[1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

Proceeding from this, I would like to find all possible combinations of these groups, and every combination of these groups should contain all provided elements. E.g.:

[[1],[2],[3]], [[1,2],[3]], [[1,3],[2]], [[1],[2,3]], [[1,2,3]]

The problem I'm running into here, is that there should be no duplicates. So, for example, a combination of [1] and [1,2] shouldn't be valid. And I'm thinking that it will be too expensive to check for the presence of duplicates by iterating over two arrays.

For additional information, I will deal with arrays of 12-13 elements.

Please advise if you know the best algorithm for this.

Andrei Chernikov
  • 360
  • 1
  • 2
  • 12
  • 3
    The keyword you're looking for is [**partition**](https://en.wikipedia.org/wiki/Partition_of_a_set). See also: [Get all the partitions of the set in python with itertools](https://stackoverflow.com/questions/42704932/get-all-the-partitions-of-the-set-python-with-itertools); [Set partitions in python](https://stackoverflow.com/questions/19368375/set-partitions-in-python/30134039) [Finding all k-subset partitions](https://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions) – Stef Oct 01 '20 at 11:10
  • The answer in my last link refers to "A very efficient algorithm (Algorithm U) is described by Knuth in the Art of Computer Programming, Volume 4, Fascicle 3B to find all set partitions with a given number of blocks." – Stef Oct 01 '20 at 11:12
  • @Stef Thanks, I didn't know the exact term for this – Andrei Chernikov Oct 01 '20 at 11:12

0 Answers0