来自层次嵌套列表的元组列表

Question

有一个内部元素的外部列表，每个所述内部元素是 flat/nested 列表。每个所述内部列表具有与前面外部单元中的内部列表相匹配的嵌套结构。这意味着列表中的每个原始值对应于一个原始值或一个列表 - 在以下单元格列表中（递归应用）。因此，每个内部列表的深度等于或超过前一个单元格中元素深度的 1。

（注意第一个单元格元素可以作为任意深度的嵌套列表开始）。

上面的例子：

[
    [[1, 2,      [3, 4]], 1           ],
    [[3, [4, 5], [6, 7]], [5, 4]      ],   
    [[5, [6, 7], [8, 9]], [7, [8, 6]] ],
]

希望将嵌套列表展开为元组列表，其中每个值与父值组合，或者如果父值是列表（保持顺序）则与相应的列表元素组合。所以对于上面的示例列表，输出应该是：

[
(1, 3, 5),
(2, 4, 6),
(2, 5, 7),
(3, 6, 8),
(4, 7, 9),
(1, 5, 7),
(1, 4, 8),
(1, 4, 6),
]

注意：这个问题是对上一个问题的扩展，但与链接问题不同的是，这里所需的元组是扁平的。

Answer 1

好的，这个怎么样：

x = [
    [[1, 2,      [3, 4]], 1           ],
    [[3, [4, 5], [6, 7]], [5, 4]      ],   
    [[5, [6, 7], [8, 9]], [7, [8, 6]] ],
]

from collections import defaultdict

def g(x):
    paths = defaultdict(lambda: [])

    def calculate_paths(item, counts):
        if type(item) is list:
            for i, el in enumerate(item):
                calculate_paths(el, counts + (i,))
        else:
            paths[counts].append(item)

    def recreate_values(k, initial_len, desired_len):
        if len(paths[k]) + initial_len == desired_len:
            yield paths[k]
        else:
            for ks in keysets:
                if len(ks) > len(k) and ks[0:len(k)] == k:
                    for ks1 in recreate_values(ks, initial_len + len(paths[k]), desired_len):
                        yield paths[k] + ks1

    for lst in x:
        calculate_paths(lst, (0,))
    keysets = sorted(list(paths.keys()))
    for k in keysets:
        yield from recreate_values(k, 0, len(x))


>>> import pprint
>>> pprint.pprint(list(g(x)))
[[1, 3, 5],
 [2, 4, 6],
 [2, 5, 7],
 [3, 6, 8],
 [4, 7, 9],
 [1, 5, 7],
 [1, 4, 8],
 [1, 4, 6]]

通过为结构中的每个数字创建一个 "path" 来工作，这是一个元组，用于标识它如何适合其特定行。

（原创尝试）：

如果一直是三层，那么是这样的？

def listify(lst):
    max_len = max(len(item) if type(item) is list else 1 for item in lst)
    yield from zip(*[item if type(item) is list else [item] * max_len for item in lst])


def f():
    for i in listify(x):
        for j in listify(i):
            for k in listify(j):
                yield k

>>> list(f())

Answer 2

这是一个需要解决的难题:-)

我确实按预期获得了不同级别的解决方案。但是，我做了一个假设：

输入的最后一列是指向其他列的指针

如果这没问题，下面的解决方案可以正常工作:-)

input = [
    [[1, 2,      [3, 4]], 1           ],
    [[3, [4, 5], [6, 7]], [5, 4]      ],
    [[5, [6, 7], [8, 9]], [7, [8, 6]] ],
]

def level_flatten(level):
    """
    This method compares the elements and their types of last column and
    makes changes to other columns accordingly
    """
    for k, l in level.items():
        size = len(l[-1]) if isinstance(l[-1], list) else 1
        # Mostly l[-1] is going to be a list; this is for just in case
        elements = l[-1]
        for i in range(-1, -len(l)-1, -1):
            elem = l[i]
            if isinstance(l[i], int):
                l[i] = [elem] * size
            else:
                for j in range(len(elem)):
                    if not isinstance(elem[j], type(elements[j])):
                        # For a list found in elements[j], there is a int at l[i][j]
                        elem[j] = [elem[j]] * len(elements[j])
    return level

level = {}

for i in range(len(input[0])):
    level[i] = []
    for j in input:
        level[i].append(j[i])

for k, l in level.items():
    for i in range(len(l[-1])):
        level = level_flatten(level)

    total_flat = []
    for item in l:
        row = []
        for x in item:
            if isinstance(x, list):
                row += x
            else:
                row.append(x)
        total_flat.append(row)
    level[k] = total_flat

output_list = []
for i in range(len(level)):# For maintaining the order
    output_list += zip(*level[i])

print output_list

我知道这不是一个很好的解决方案，可以进一步优化。我正在想一个比这更好的算法。如果我找到更好的解决方案，将会更新:-)

Answer 3

我首先尝试使用 2d 矩阵解决这个问题，但结果是迭代最后一行分割它上面的列段更简单：

def unfold(ldata):
    ''' 
    ldata: list of hierarchical lists.
    technique: repeatedly flatten bottom row one level at a time, unpacking lists or
    adding repeats in the column above at the same time. 
    convention: n=1 are primitives, n>=2 are lists.
    '''

    has_lists = True
    while has_lists:
        has_lists = False 
        for i, elm in enumerate(ldata[-1]):
            if type(elm) is list:
                has_lists = True
                ldata[-1][i:i+1] = ldata[-1][i] # unpack
                for k in range(0, len(ldata)-1): # over corresponding items in above column
                    if type(ldata[k][i]) is list:
                        ldata[k][i:i+1] = ldata[k][i] # unpack
                    else:
                        ldata[k][i:i+1] = [ldata[k][i]]*len(elm) # add repeats
    return list(zip(*ldata))            

x = [
    [[1, 2,      [3, 4]], 1           ],
    [[3, [4, 5], [6, 7]], [5, 4]      ],   
    [[5, [6, 7], [8, 9]], [7, [8, 6]] ],
]

from pprint import pprint
pprint(unfold(x))

>>>
[(1, 3, 5),
 (2, 4, 6),
 (2, 5, 7),
 (3, 6, 8),
 (4, 7, 9),
 (1, 5, 7),
 (1, 4, 8),
 (1, 4, 6)]

来自层次嵌套列表的元组列表

List of tuples from heirarchical nested lists

python

nested

tuples

list