1

我有一个格式如下的列表列表。

[[1,3],[2,4],[3,1],[4,0],[5,1],[6,0],[7,1],[8,0],[ 9,1],[10,0],[11,3],[12,1],[13,0],[14,1],[15,0],[16,1],[17, 0],[18,4],[19,1],[20,0],[21,1],[22,0],[23,1],[24,2],[25,0] ,[26,0],[27,1],[28,0]......]

或以图形方式，我的输入列表是：

[1,3]
    [2,4]
        [3,1]
            [4,0]
        [5,1]
            [6,0]
        [7,1]
            [8,0]
        [9,1]
            [10,0]
    [11,3]
        [12,1]
            [13,0]
        [14,1]
            [15,0]
        [16,1]
            [17,0]
    [18,4]
        [19,1]
            [20,0]
        [21,1]
            [22,0]
        [23,1]
            [24,2]
                [25,0]
                [26,0]
        [27,1]
            [28,0]

在上面的输入中，列表的第一个值（零位置）是项目序列（你可以从上到下看到它们），第二个值是它拥有的孩子的数量！

我希望我的输出在第三个值（第二个位置）中我希望它的父级如下例所示......

我想得到如下输出： [[1,3,0],[2,4,1],[3,1,2],[4,0,3],[5,1,2],[ 6,0,5],[7,1,2],[8,0,7],[9,1,2],[10,0,9],[11,3,1],[12, 1,11],[13,0,12],[14,1,11],[15,0,14],[16,1,11],[17,0,16],[18,4, 1],[19,1,18],[20,0,19],[21,1,18],[22,0,21],[23,1,18],[24,2,23] ,[25,0,24],[26,0,24],[27,1,18],[28,0,27].....]

以图形方式所需的输出：

[1,3,0]
    [2,4,1]
        [3,1,2]
            [4,0,3]
        [5,1,2]
            [6,0,5]
        [7,1,2]
            [8,0,7]
        [9,1,2]
            [10,0,9]
    [11,3,1]
        [12,1,11]
            [13,0,12]
        [14,1,11]
            [15,0,14]
        [16,1,11]
            [17,0,16]
    [18,4,1]
        [19,1,18]
            [20,0,19]
        [21,1,18]
            [22,0,21]
        [23,1,18]
            [24,2,23]
                [25,0,24]
                [26,0,24]
        [27,1,18]
            [28,0,27]

怎么解决？

4

3 回答 3

3

你可以用这样的迭代器来做到这一点：

def add_parent_info(it, parent=0):
    me, num_children = it.next() # For Python 3.x use next(it)
    yield [me, num_children, parent]
    for i in range(num_children):
        for item in add_parent_info(it, me):
            yield item

用法：

>>> a = [[1,3],[2,4],[3,1],[4,0],[5,1],[6,0],[7,1],[8,0],[9,1],[10,0],[11,3],[12,1],[13,0],[14,1],[15,0],[16,1],[17,0],[18,4],[19,1],[20,0],[21,1],[22,0],[23,1],[24,2],[25,0],[26,0],[27,1],[28,0]]
>>> print list(add_parent_info(iter(a)))
[[1, 3, 0], [2, 4, 1], [3, 1, 2], [4, 0, 3], [5, 1, 2], [6, 0, 5], [7, 1, 2], [8, 0, 7], [9, 1, 2], [10, 0, 9], [11, 3, 1], [12, 1, 11], [13, 0, 12], [14, 1, 11], [15, 0, 14], [16, 1, 11], [17, 0, 16], [18, 4, 1], [19, 1, 18], [20, 0, 19], [21, 1, 18], [22, 0, 21], [23, 1, 18], [24, 2, 23], [25, 0, 24], [26, 0, 24], [27, 1, 18], [28, 0, 27]]
于 2012-04-06T09:18:20.373 回答
1

编辑：@WolframH 具有生成结构的最佳解决方案。您可以通过将其优雅的解决方案与 Node 对象结构相结合，将其更改__init__为：

def __init__(self,value,parent_value,child_value,list_of_children):
    self.value=value
    self.parent_value = parent_value
    self.child_value = child_value
    self.children = list_of_children

使用 @WolframH 的生成结构的方法，并遍历所有在其上调用 Node 构造函数的条目。这样，您可以更容易地插入和删除项目。

您需要定义一个数据结构（想到一棵树）并将值存储在其中。我建议使用树，将节点类应用到树的下方。（您可以定义一种称为叶子的不同格式，但不会真正有所作为。

class Node(object):
    def __init__(self,val,list_of_children,parent_value)
        self.value = val
        self.children = make_children(list_of_children,val)
        self.parent_value = parent_value

    # in case number of children changes, don't generate middle value
    # until necessary
    def get_list_of_values(self):
        [self.value,len(children),self.parent_value]

    def add_child(self, child):
        self.children.append(child)

    def change_value(self,new_value):
        """update children to reflect changed value"""
        self.value = new_value
        def fn(child):
            child.parent_value = new_value
        map(fn,self.children)


def make_children(list_of_children,parent_value):
    child_list=[]
    # recursive-ish case: there are children
    if list_of_children:
        for child in list_of_children:
            # presuming initially stored as list of lists, e.g. 
            #    [node_value,[node[leaf][leaf]],[node,[node[leaf]],[leaf]]
            #    so child[0] is value, and rest are children
            value = child.pop(0)
            child_list.append(Node(value,child,parent_value)))
        return child_list
    # base case: no children - so return empty set
    else:
        return []
于 2012-04-06T07:07:04.907 回答
1

@WolframH 有使用迭代器的最佳解决方案，我将把它留在这里作为不使用迭代器的低效示例：D

>>> stuff = [[1,3],[2,4],[3,1],[4,0],[5,1],[6,0],[7,1],[8,0],[9,1],[10,0],[11,3],[12,1],[13,0],[14,1],[15,0],[16,1],[17,0],[18,4],[19,1],[20,0],[21,1],[22,0],[23,1],[24,2],[25,0],[26,0],[27,1],[28,0]]
>>> def walk(parent, i, items):
        item_seq, num_children = items[i]
        children = [items[i]+[parent]]
        for _ in range(num_children):
            i,child = walk(item_seq,i+1,items)
            children.extend(child)
        return i, children

>>> walk(0,0,stuff)[1]
[[1, 3, 0], [2, 4, 1], [3, 1, 2], [4, 0, 3], [5, 1, 2], [6, 0, 5], [7, 1, 2], [8, 0, 7], [9, 1, 2], [10, 0, 9], [11, 3, 1], [12, 1, 11], [13, 0, 12], [14, 1, 11], [15, 0, 14], [16, 1, 11], [17, 0, 16], [18, 4, 1], [19, 1, 18], [20, 0, 19], [21, 1, 18], [22, 0, 21], [23, 1, 18], [24, 2, 23], [25, 0, 24], [26, 0, 24], [27, 1, 18], [28, 0, 27]]
于 2012-04-06T08:44:12.297 回答