如何分割两个嵌套列表并合并部分以创建两个新嵌套列表

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

如果你在每个内部节点里存储一个数字，这个数字代表了每个分支下的孩子节点数量，那么你就可以通过生成一个从0到1加上总孩子数量的随机数来选择一个分裂点。如果这个随机数是1，就在那个节点进行分裂；如果不是1，就用这个数字来判断应该往哪个子树走，然后再重复这个过程。

Answer 2

我最后把大部分内容当作练习实现了。

首先，找出可以拆分的位置数量：也就是非函数节点的数量。

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] 里，这样可编辑的节点总是会有一个父节点。

不过，这个方法效率不是很高。维护节点数量可能会让它更快，但那样的话你还需要存储父节点的引用，以便有效更新数量。如果你选择这个方向，真的很需要找到或实现一个真正的树类。