二つの新しいネストされたリストを作成するために、2つのネストされたリストを分割し、部品を組み合わせる方法

Question

私はPythonで、単純な遺伝的プログラミングユーティリティをコーディングしようとしています。しかし、今、私は私の木のためのクロスオーバー/メイト機能にこだわっています。木がネストされたリストによって構築されており、このような何かを見ているます：

# f = internal node (a function), c = leaf node (a constant)
tree1 = [f, [f, [f, c, c], [f, c, c]], [f, [f, c, c], [f, c, c]]]
tree2 = [f, [f, [f, c, c], c], [f, [f, c, c], c]]

私はランダムで分割し、各ツリー内のポイントを選択したいと、私はそれぞれの木から一つの部分は、新しいツリーにまとめることにしたいです。それはあまりにも大きなツリーを作成することができますよう選択が本当にツリー内のどこにでも場所を取ることができないので、超えてはならない最大深さもあります。以下は、それが動作するはずです方法の例です。

# f:n, where n is the number of arguments the function take
#               + split here  
tree1 = [f:2, [f:3, a, a, a], a]
#                            + split here
tree2 = [f:2, [f:2, a, a], [f:1, a]

tree_child1 = [f:2, [f:1, a], a]
tree_child2 = [f:2, [f:2, a, a], [f:3, a, a, a]]

私はこの問題を解決する方法については（現時点では）見当がつかない。任意のヒントや解決策は歓迎以上です！

（それは誰かがより良い構造を理解するのに役立つかもしれないと私の解析機能を追加しました。）

# My recursive code to parse the tree.
def parse(self, node=None):
    if not node:
        node = self.root

    if isinstance(node, list):
        function = node[0]
        res = []
        for child in node[1:function.arity+1]:
            res.append(self.parse(child))
        value = function.parse(*res) # function
    else:
        value = node.parse() # constant
    return value

Answer 1

私は運動としてのほとんどを実装してしまっています。

まず、分割する可能な位置の数を見つける：非機能ノードの数を

def count(obj):
    total = 0
    for o in obj[1:]:
        # Add the node itself.
        total += 1

        if isinstance(o, list):
            total += count(o)
    return total

次に、ヘルパー：それがどこにある上記の範囲内のインデックス指定された、把握

。

def find_idx(tree, idx):
    """
    Return the node containing the idx'th function parameter, and the index of that
    parameter.  If the tree contains fewer than idx parameters, return (None, None).
    """
    if not isinstance(idx, list):
        # Stash this in a list, so recursive calls share the same value.
        idx = [idx]

    for i, o in enumerate(tree):
        # Skip the function itself.
        if i == 0:
            continue

        if idx[0] == 0:
            return tree, i

        idx[0] -= 1
        if isinstance(o, list):
            container, result_index = find_idx(o, idx)
            if container is not None:
                return container, result_index

    return None, None

スワップを行うと、今非常に簡単です。

def random_swap(tree1, tree2):
    from random import randrange
    pos_in_1 = randrange(0, count(tree1))
    pos_in_2 = randrange(0, count(tree2))

    parent1, idx1 = find_idx(tree1, pos_in_1)
    parent2, idx2 = find_idx(tree2, pos_in_2)

    # Swap:
    parent1[idx1], parent2[idx2] = parent2[idx2], parent1[idx1]

c = 1
tree1 = ["f:2", c, ["f:1", c]]
tree2 = ["f:2", ["f:2", ["f:2", c, c], ["f:2", c, c]], ["f:3", ["f:4", c, c, c, c], ["f:2", c, c], c]]

while True:
    random_swap(tree1, tree2)
    print tree1
    print tree2

これは、最大深さを実装していないが、それはスタートだ。

これはまた、tree1というにおけるノードが新たな樹上村になり、樹上村のすべてがtree1というにおけるノードとなるルートノードを置き換えることはありません。この問題を回避するには、例えば全体の事をラップすることです。 [ラムダA：、木]、その編集可能なノードは、常に親ノードを持っている。

。

これは非常に効率的ではありません。ノード数を維持することは、それはより速く作ることができますが、その後、あなたは効率的にカウントを更新するためには、あまりにも、親への参照を格納する必要があると思います。あなたはそのルートを行く場合は、あなたが本当に探したり、本物の木のクラスを実装することをお勧めします。

Answer 2

あなたは各内部ノードに各ブランチの子供の数を格納した場合、あなたは0 + 1の合計子供から乱数を発生させることにより、スプリットポイントを選ぶことができます。答えが1である場合、に下降し、処理を繰り返すたサブツリー把握する番号を使用してそれ以外の場合は、そのノードで分割します。