Combinatorics In Python

I have a sort of a one level tree structure as: Where p are parent nodes, c are child nodes and b are hypothetical branches. I want to find all combinations of branches under the

Solution 1:

Here's one way to do it. There are lot's of micro-optimizations that could be made but their efficacy would depend on the sizes involved.

import collections as co
import itertools as it

defunique(list_):
    returnlen(set(list_)) == len(list_)

defget_combos(branches):
    by_parent = co.defaultdict(list)

    for branch in branches:
        by_parent[branch.p].append(branch)

    combos = it.product(*by_parent.values())

    return it.ifilter(lambda x: unique([b.c for b in x]), combos)

I'm pretty sure that this is at least hitting optimal complexity as I don't see a way to avoid looking at every combination that is unique by parent.

Solution 2:

Look at itertools combinatoric generators:

• product()
• permutations()
• combinations()
• combinations_with_replacement()

Looks like you can write an iterator to achieve what you want.