I'm trying to create a function which takes a list of subsets, and merge them into larger sets if all combinations are present.
Basically, let's say we have n=4 (i.e index_domain = {0,1,2,3}) and we have the following combinations as input
[(0, 2), (0, 3), (1, 3), (2, 3)]
the function should take this input and generate the following output:
[(0, 2, 3), (1, 3)]
So, (0, 2, 3) since all of the combinations (combination of 2) are present in the input list. (1, 3) remains as is since we don't have another combination of 1.
For an index domain D ⊆ ℕ and input list L, the main features of the case are:
- L can be an empty list. (Off topic)
- L always contains combination of 2s, i.e pairs, if not empty.
- The pairs are symmetric and only one of the pairs are included in L (no duplicates). That is, if a pair (i, j) should be included in L, then pair (i, j) is present in L and (j, i) is never included, where i < j and i, j ∈ D.
- There is never a pair (i, i) in L, i ∈ D.
Simply it is combinations(n, 2) in reverse. I have searched for this topic "reverse combinations", and I've yet to find an appropriate resource so far. I've considered some options like double iteratation of the input to check if all combinations are there, but that's not the best way of doing it. I've yet to come up with an efficient solution. Appreciate any idea for an effective solution.
Thanks.