6

私は一種の1レベルのツリー構造を次のように持っています:

代替テキスト

ここで、p は親ノード、c は子ノード、b は仮想分岐です。

1 つの親のみが1つの子ノードにのみ分岐でき、2 つの分岐は親および/または子を共有できないという制約の下で、分岐のすべての組み合わせを見つけたいと考えています。

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

それがすべてだと思います。=)

この構造の任意のツリー、つまり p:s、c:s、および b:s の数は任意です。

編集：

これはツリーではなく、二部 有向非巡回グラフです

4

2 に答える 2

5

これを行う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)

親によって一意であるすべての組み合わせを見ることを避ける方法がわからないため、これが少なくとも最適な複雑さに達していると確信しています。

于 2010-11-04T11:11:35.280 に答える
4

itertools コンビナトリックジェネレーターを見てください。

  • 製品（）
  • 順列()
  • 組み合わせ()
  • 組み合わせ_と_置換()

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

于 2010-11-04T10:43:10.770 に答える