如何拆分两个嵌套列表并组合这些部分以创建两个新的嵌套列表

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，则在该节点处进行拆分，否则使用该数字计算出要下降的子树，然后重复该过程。