python - 如何将这些嵌套的 for 循环变成单个循环？

Question

我有这个列表:

ls = [[0, 'C', [1, 2, 3, 4], 'E', []],
      [1, 'C', [0, 5, 6, 7], 'E', []],
      [2, 'H', [0], '-', []],
      [3, 'H', [0], '-', []],
      [4, 'H', [0], '-', []],
      [5, 'H', [1], '-', []],
      [6, 'O', [1], 'X', []],
      [7, 'H', [1], '-', []]]

这代表一个分子。第一列只是一个数字，第二列是分子中的一个原子，第三列告诉这个原子与哪些原子结合。例如，原子 0 绑定(bind)到原子 1、2、3 和 4。我想找出每个原子与氧气的距离，这是存储到最后一列的信息。所以输出应该是:

[[0, 'C', [1, 2, 3, 4], 'E', 2],
[1, 'C', [0, 5, 6, 7], 'E', 1],
[2, 'H', [0], '-', 3],
[3, 'H', [0], '-', 3],
[4, 'H', [0], '-', 3],
[5, 'H', [1], '-', 2],
[6, 'O', [1], 'X', 0],
[7, 'H', [1], '-', 2]]

我试过这个循环，它工作得很好:

def dists(data):
    new_data = data
    # Loop to find the distances from the X-atom:
    for sl2 in new_data:
        if sl2[3] == "X":
            sl2[4] = 0
            next1 = sl2[2]

    for number1, row1 in enumerate(new_data):
        for a1 in next1:
            if new_data[number1][0] == a1:
                if type(new_data[a1][4]) == list:
                    new_data[a1][4] = 1
                    next2 = new_data[a1][2]

                    for number2, row2 in enumerate(new_data):
                        for a2 in next2:
                            if new_data[number2][0] == a2:
                                if type(new_data[a2][4]) == list:
                                    new_data[a2][4] = 2
                                    next3 = new_data[a2][2]

                                    for number3, row3 in enumerate(new_data):
                                        for a3 in next3:
                                            if new_data[number3][0] == a3:
                                                if type(new_data[a3][4]) == list:
                                                    new_data[a3][4] = 3
                                                    next4 = new_data[a3][2]
                                                        #etc...
    return new_data

ls2 = dists(ls)

但现在我必须制作许多嵌套的 for 循环。如何将这些嵌套循环变成单个循环？

编辑@deadshot

第五列的值来自于这些:

sl2[4] = 0
new_data[a1][4] = 1
new_data[a2][4] = 2
new_data[a3][4] = 3
etc...

在第四列中，“X”只是帮助我找到氧原子的起点。

Answer 1

在计算机科学术语中，您所拥有的就是所谓的图形。你的分子就是所谓的“节点”或“顶点”，它们之间的连接被称为“边”。您需要找到氧气与所有其他节点之间的距离。这可以通过所谓的 Breadth first search 来完成。 (还有其他方法，但我认为这是最容易入手的方法)

我强烈建议你阅读关于此的维基百科页面，但这里有一个适合你的数据结构的 python 版本:

from collections import deque


def bfs(ls):
    root = [a for a,b, *(_) in ls if b == 'O' ][0]
    ls[root][4] = 0 # mark oxygen as distance 0
    queue = deque([(root,0)])
    discovered = set([root])
    
    while queue:
        v,d = queue.popleft()
        for edge in ls[v][2]:
            if edge not in discovered:
                discovered.add(edge)
                queue.append((edge,d+1))
                ls[edge][4] = d+1 # add distance to new atom
            

像这样运行:

bfs(ls)

ls 运行后:

[[0, 'C', [1, 2, 3, 4], 'E', 2],
 [1, 'C', [0, 5, 6, 7], 'E', 1],
 [2, 'H', [0], '-', 3],
 [3, 'H', [0], '-', 3],
 [4, 'H', [0], '-', 3],
 [5, 'H', [1], '-', 2],
 [6, 'O', [1], 'X', 0],
 [7, 'H', [1], '-', 2]]

尾注:您可以利用您的数据结构来避免将 discovered 用作单独的变量，但我将其包含在此处以更符合 wiki 页面上的伪代码。这样更容易比较 python 代码和理论。