0

Maybe I'm missing some simple answer. Task - we have a set of size n*k, need to get a list of lists (size n) of sets (size k) with all possible combinations for splitting the set into parts of this size.

Sample:

Set:

(1,2,3,4,5,6)

Size: 3

Expected result:

[[(1,2,3),(4,5,6)],
[(1,2,4),(3,5,6)],
[(1,2,5),(3,4,6)],
[(1,2,6),(3,4,5)],
[(1,3,4),(2,5,6)],
[(1,3,5),(2,4,6)],
[(1,3,6),(2,4,5)],
[(1,4,5),(2,3,6)],
[(1,4,6),(2,3,5)],
[(1,5,6),(2,3,4)]]

The only thing that comes to mind is to find all subsets of size k and group them into lists taking only these that contain non-repeating elements.

bylazy
  • 1,055
  • 1
  • 5
  • 16
  • 1
    There are simple algorithms to generate all combinations of distinct elements directly. See for instance https://docs.python.org/3/library/itertools.html#itertools.combinations – Stef Feb 11 '23 at 20:04
  • You can get a recurrence formula, and then use it to write an algorithm. Note comb(S, k) the set of all size-k combinations of set S. If S is a set and x is an element of S, then a combination of S either doesn't contain x or contains x. Hence: `comb(S, k) = comb(S \{x}, k) + { {x} + c | c in comb(S\{x}, k-1) }`. (where `+` is set union and `\ ` is set difference). – Stef Feb 11 '23 at 20:08
  • This question might be related. Here's a generalised answer: https://stackoverflow.com/a/53684018/2034787 – גלעד ברקן Feb 13 '23 at 13:26

0 Answers0