# Optimal coalition structure

The problem is the following: if there is a set `S = {x1, ..., x_n}` and a function `f`: set -> number, which takes a set as an input and returns a number as an output, what is the best possible coalition structure (coalition structure a set of subsets of a `S`.That is, find the subsets,such that the sum of `f(s_i)` for every subset `s_i` in `S` is maximal). The sets in the coalition should not overlap and their union should be `S`. A template is this:

```def optimal_coalition(coalitions):
"""
:param coalitions: a dictionary of the form {coalition: value}, where coalition is a set, and value is a number
:return:
"""

optimal_coalition({set(1): 30, set(2): 40, set(1, 2): 71}) # Should return set(set(1, 2))
```

This is from a paper I found:

I transliterated the pseudocode. No doubt you can make it better — I was hewing very closely to show the connection.

I did fix a bug (`Val(C') + Val(C C') > v(C)` should be `Val(C') + Val(C C') > Val(C)`, or else we may overwrite the best partition with one merely better than all of `C`) and two typos (`C / C'` should be `C C'`; and `CS*` is a set, not a tree).

```import itertools

def every_possible_split(c):
for i in range(1, len(c) // 2 + 1):
yield from map(frozenset, itertools.combinations(tuple(c), i))

def optimal_coalition(v):
a = frozenset(x for c in v for x in c)
val = {}
part = {}
for i in range(1, len(a) + 1):
for c in map(frozenset, itertools.combinations(tuple(a), i)):
val[c] = v.get(c, 0)
part[c] = {c}
for c_prime in every_possible_split(c):
if val[c_prime] + val[c - c_prime] > val[c]:
val[c] = val[c_prime] + val[c - c_prime]
part[c] = {c_prime, c - c_prime}
cs_star = {a}
while True:
for c in cs_star:
if part[c] != {c}:
cs_star.remove(c)
cs_star.update(part[c])
break
else:
break
return cs_star

print(
optimal_coalition({frozenset({1}): 30, frozenset({2}): 40, frozenset({1, 2}): 69})
)
```