Комбинаторика в Питоне

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]]

Я думаю, что это все их. знак равно

Как это может быть автоматически достигнуто в Python для произвольных деревьев этой структуры, то есть количество P: S, C: S и B: S произвольно.

РЕДАКТИРОВАТЬ:

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

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 Комбинаторные генераторы:

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

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