Pythonの組み合わせ

Question

私は次のような1つのレベルのツリー構造を持っています：

ここで、pは親ノード、cは子ノード、bは 仮説 枝。

すべてを見つけたいです 組み合わせ 制約の下での枝のみ 1 親はのみ分岐できます 1 子ノード、および2つの枝は親や子を共有できません。

例：if 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で、これをPythonで自動的に痛むことができますか？つまり、P：S、C：S、およびB：Sの数は任意です。

編集：

それは木ではなく、むしろです 二部 指示された非環式グラフ

Answer 1

これが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（）

あなたが望むものを達成するためにイテレーターを書くことができるようです。