Question: How to generate all 3-subsets that satisfy certain conditions without post-filtering?

Edits: In fact it is a set partition problem.


I have the following subsets: 


I want to divide the set into 2 groups such that each group has exactly 3 elements. We want to generate all solutions. Note that we treat ({"a", "b", "c"}|{"d", "e", "f"}) and ({"d", "e", "f"}|{"a", "b", "c"}) as the same solution.

So first I used the choose function to generate all 3-subsets and then filtered for duplicate solutions.

l:=[ListTools:-Categorize((x,y)-> is(x =`minus`(s, y)),M)]:

{"a", "b", "c"}, {"a", "b", "d"}, {"a", "b", "e"}, {"a", "b", "f"}, {"a", "c", "d"}, {"a", "c", "e"}, {"a", "c", "f"}, {"a", "d", "e"}, {"a", "d", "f"}, {"a", "e", "f"}

But I feel like the solution is a bit inefficient. In fact, we only need half of all 3-subsets. I wonder if we can only keep one representative member of the same  solutions when generating the 3-subsets.

 In fact, the problem can be generalized as follows: given a list of n elements, divide it into m groups and generate all solutions. Similarly,  the same solution is generated only once. 

Please Wait...