## Saturday, November 8, 2008

### 99 problems - python - 27

Group the elements of a set into disjoint subsets.

a) 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) )
... )

b) 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) )
... )
`def combination(lst, size):    #defined as in previous problemdef grouped_combos(lst, sizes):    assert len(lst) == sum(sizes)    if not sizes:        yield []    else:        for combo in combinations(lst, sizes[0]):            rest = sorted(list(set(lst) - set(combo)))            for rest_combo in grouped_combos(rest, sizes[1:]):                yield [combo] + rest_combo`

I have a sorted thrown in since using set gave unreliable ordering after the set difference. I really love recursion. It seems like the above would be quite annoying without it.