从列表创建图表

Question

我有一个这样的列表：

a=[
   ["x", "x", 0,  0, "x", "x"],
   [ 0,   0,  0,  0, "x", "x"],
   ["x", "x", 0,  0,  0,  "x"],
   ["x", "x", 0,  0,  0,   0 ]
]

我希望列表中相互连接的任何 x 都在一个组中。

示例：

组 1 = (0,0),(0,1)
组 2 = (0,4),(0,5),(1,4),(1,5),(2,5)
组 3 = (2,0),(2,1),(3,0),(3,1)

解决方法是什么？

我怎么知道两组之间哪条路径最短？

Answer 1

对于 Q1，您可以使用与坐标关联的列表逐行逐列地浏览矩阵以形成组。将每个坐标放在当前坐标上方或左侧的连接位置列表中。没有连接时创建一个新的列表（组），当位置连接两个不同的组时合并列表。

a=[
   ["x", "x", 0, 0, "x","x"],
   [ 0,   0,  0, 0, "x","x"],
   ["x", "x", 0, 0,  0, "x"],
   ["x", "x", 0, 0,  0,  0 ]
]

groups = dict()                    # group (list) at each coordinate
for r,row in enumerate(a):
    for c,v in enumerate(row):
        above = groups[r-1,c] if r and a[r-1][c] == v else None     
        left  = groups[r,c-1] if c and a[r][c-1] == v else None
        if above and left and above is not left:
            above.extend(left)     # merge left into above group
            for rc in left: groups[rc] = above             
        g = above or left or []    # select existing group or new
        g.append((r,c))            # add r,c to selected group
        groups[r,c] = g            # identify coordinate's group

# extract distinct groups from coordinate assignments
groups = list({id(g):g for g in groups.values()}.values())

输出：

# all groups (i.e. groups of "x"s and groups of 0s)
print(groups)
[[(0, 1), (0, 0)], 
 [(1, 2), (3, 2), (1, 3), (3, 5), (3, 3), (0, 2), 
  (2, 4), (2, 3), (2, 2), (1, 0), (3, 4), (1, 1), (0, 3)], 
 [(1, 4), (1, 5), (0, 5), (0, 4), (2, 5)], 
 [(3, 0), (2, 0), (3, 1), (2, 1)]]

# only "x" groups
xGroups = [g for g in groups if a[g[0][0]][g[0][1]] == "x"]
print(xGroups)
[[(0, 1), (0, 0)], 
 [(1, 4), (1, 5), (0, 5), (0, 4), (2, 5)], 
 [(3, 0), (2, 0), (3, 1), (2, 1)]]

对于Q2，您可以编写一个函数，通过扩展第一组的每个坐标可以到达第二组的任何坐标而仅经过0个位置的路径来找到两组之间的距离（技术上 breadth-first search）：

def distance(a,g1,g2):
    rows = len(a)
    cols = len(a[0])
    distance = 1
    seen     = set(g1) # track visited coordinates
    paths    = g1      # current reach, starts with g1 coordinates
    while paths:
        nextPaths = set()
        for r,c in paths:
            for nr,nc in [(r,c-1),(r,c+1),(r-1,c),(r+1,c)]: #neighbours
                if nr not in range(rows): continue
                if nc not in range(cols): continue
                if (nr,nc) in seen: continue        # no doubleback
                if (nr,nc) in g2: return distance   # g2 reached
                if a[nr][nc] == 0:
                    nextPaths.add((nr,nc))          # advance on 0s
                    seen.add((nr,nc))
        distance += 1                  # g2 not reached, need more steps
        paths = nextPaths              # start from positions reached so far
    return None

print(distance(a,xGroups[0],xGroups[1])) # 3
print(distance(a,xGroups[1],xGroups[2])) # 4            
print(distance(a,xGroups[0],xGroups[2])) # 2

Answer 2

我发布的 Q1 算法效率稍低，但可读性可能更好。

它从任意 "X" 开始，然后添加它的邻居，然后是邻居的邻居等等，直到没有更多的邻居，即找到整组相邻的 "X"。

def neigh4(c):
    i, j = c 
    yield (i-1, j)
    yield (i+1, j)
    yield (i, j-1)
    yield (i, j+1)

def groups(array):
    coords = { 
        (i,j) for i in range(len(array)) for j in range(len(array[0]))
        if array[i][j] == "x"}
    while coords:
        group = set()
        wset = {next(iter(coords))} # arbitrary member
        while wset:
            member = wset.pop()
            wset.update(c for c in neigh4(member) if c in coords)
            coords.remove(member)
            group.add(member)
        yield group

print(list(groups(a))) # "a" from the question

个人说明：30 多年前，我们在编程竞赛（BASIC！）中接受了这项练习。我15岁没解决。

从列表创建图表

Creating a graph from the list

python

graph

list