P27: Group the elements of a set into disjoint subsets

L-99 is a list of Prolog challenges with solutions in Lisp. However, the solutions you can find here are written in q.

In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities and returns them in a list.

Example
* (group3 '(aldo beat carla david evi flip gary hugo ida))
( ( (ALDO BEAT) (CARLA DAVID EVI) (FLIP GARY HUGO IDA) )
... )


Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.

Example
* (group '(aldo beat carla david evi flip gary hugo ida) '(2 2 5))
( ( (ALDO BEAT) (CARLA DAVID) (EVI FLIP GARY HUGO IDA) )
... )

Note that we do not want permutations of the group members; i.e. ((ALDO BEAT) …) is the same solution as ((BEAT ALDO) …). However, we make a difference between ((ALDO BEAT) (CARLA DAVID) …) and ((CARLA DAVID) (ALDO BEAT) …).

You may find more about this combinatorial problem in a good book on discrete mathematics under the term “multinomial coefficients“.

qSolution

In both functions I am using comb function to generate combinations of K distinct objects chosen from N elements of a list. First the special case – 3 disjoint subgroups of 2, 3 and 4 elements:

group3:{[list]
  if[9<>count list;'"length";];
  tmp:list except/:s2:list comb[count list;2];
  :raze (enlist each s2),/:'(enlist @/:'s3),''enlist@/:'tmp except/:'s3:tmp@\:comb[count tmp[0];3];
  };

Example
group3 `a`b`c`d`e`f`g`h`i
`a`b `c`d`e `f`g`h`i
`a`b `c`d`f `e`g`h`i
`a`b `c`e`f `d`g`h`i
`a`b `d`e`f `c`g`h`i
`a`b `c`d`g `e`f`h`i
`a`b `c`e`g `d`f`h`i
..


I am expecting to get 1260 distinct groups (see: multinomial coefficients):

count group3 `a`b`c`d`e`f`g`h`i
1260


Just to make sure they are really distinct:
count distinct group3 `a`b`c`d`e`f`g`h`i
1260


qSolution

And now the generalized version which is using recursion. I split the function into two – groups is the one that generates all the groups and subsets is a wrapper that adds one-time basic validation of parameters.

groups:{[list;lengths]
  c:list comb[count list;first lengths];
  if[2=count lengths;
    :flip ((),c;list except/:c);
    ];
  :raze (enlist each c),/:'.z.s ./:(enlist each list except/:c),\:enlist 1_lengths;
  };

subsets:{[list;lengths]
  if[any not 0<lengths;'"type"];
  if[(c:count list)<>sum lengths;'"length"];
  if[all c=lengths;:list];
  :groups[list;lengths];
  };


Example
subsets[`a`b`c`d`e`f`g`h`i;2 3 4]
`a`b `c`d`e `f`g`h`i
`a`b `c`d`f `e`g`h`i
`a`b `c`e`f `d`g`h`i
`a`b `d`e`f `c`g`h`i
`a`b `c`d`g `e`f`h`i
..


Again I am getting 1260 distinct groups:

count subsets[`a`b`c`d`e`f`g`h`i;2 3 4]
1260
count distinct subsets[`a`b`c`d`e`f`g`h`i;2 3 4]
1260


And yes, there is a difference between ((`a`b);(`c`d)…) and ((`c`d);(`a`b)…):

subsets[`a`b`c`d`e`f`g`h`i;2 2 5]
`a`b `c`d `e`f`g`h`i
`a`b `c`e `d`f`g`h`i
..
`c`d `a`b `e`f`g`h`i
`c`d `a`e `b`f`g`h`i
..