Комбинаторика в Python

Question

У меня есть одноуровневая древовидная структура:

Где p - родительские узлы, c - дочерние узлы, а b - гипотетические ветви.

Я хочу найти все комбинации ветвей при условии, что только один родитель может перейти только к одному дочернему узлу, а две ветви не могут совместно использовать родитель и / или ребенок.

например. если combo - набор комбинаций:

combo[0] = [b[0], b[3]]
combo[1] = [b[0], b[4]]
combo[2] = [b[1], b[4]]
combo[3] = [b[2], b[3]]

Я думаю, что это все из них. =) * +1022 *

Как это может быть достигнуто автоматически в Python для произвольных деревьев этой структуры, то есть число p: s, c: s и b: s произвольно.

EDIT:

Это не дерево, а двудольный направленный ациклический граф

Answer 1

Вот один из способов сделать это. Существует множество микрооптимизаций, которые могут быть выполнены, но их эффективность будет зависеть от размеров.

import collections as co
import itertools as it

def unique(list_):
    return len(set(list_)) == len(list_)

def get_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)

Я почти уверен, что это по крайней мере достигает оптимальной сложности, поскольку я не вижу способа избежать рассмотрения каждой комбинации, уникальной для родителя.

Answer 2

Посмотрите на itertools комбинаторные генераторы:

• продукт ()
• Перестановки ()
• комбинация ()
• combinations_with_replacement ()

Похоже, вы можете написать итератор для достижения того, чего вы хотите.