2つの入れ子リストを分割し、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のノードが新しいtree2になり、tree2のすべてがtree1のノードになります。回避策は、例えば全体を包むことです。 [lambda a：a、tree]なので、編集可能なノードには常に親ノードがあります。

これはあまり効率的ではありません。ノード数を維持すると、それをより速くすることができますが、カウントを効率的に更新するには、親への参照も保存する必要があります。そのルートに行くなら、実際のツリークラスを見つけたり実装したりしたいと思うでしょう。

Answer 2

あなたは、各内部ノードに各ブランチの子供の数を保存する場合は、あなたがスプリットを選ぶことができ0から1 +全子供までの乱数を生成することにより、答えが1の場合は、そのノードで分割し、そうでなければその番号を使用して、下位になるサブツリーを決定し、プロセスを繰り返します。