Python中的对角网格遍历

Question

为清晰起见进行了编辑

我到处找这个，但什么也没找到。我希望遍历一个2D字符串列表，并像这里那样显示片段Traverse 2D Array (Matrix) Diagonally，但使用python。在

lines = ['xmfycxvc',
         'caubmekv',
         'awactivb',
         'paphzkcn',
         'sbsaakjy',
         'tsewlhvk']
diagonals = []
i = 0
while i < len(lines):
   j = 0
   diagonal = ''
   while j < len(lines[0]):
      diagonal += lines[j][j]
      i += 1
diagonals.append(diagonal)
print(diagonals)

我知道我的索引是错误的，但我尝试了一切，仍然不能使它像链接。最接近的是每个对角线都有，但是它也会像这样的球体一样环绕着矩阵，但我不想这样。在

我想对角遍历字符串矩阵并打印对角线，例如['x','cm','aaf','pwuy','saabc','tbpcmx','sshtev','eazikc','wakvv','lkcb','hjn','vy','k']及其从左上到右的计数器部分。在

Answer 1

根据一点推理，我们得到矩阵中每一条对角线的列数（或后面的x）和行号（y）之间的差是恒定的。我们可以使用一个collections.defaultdict作为我们的数据结构，它被自动初始化为一个空列表，在所有矩阵元素上有一个循环，找到每个元素所属的对角线，并将这些元素列在我们的defaultdict中。在

def getdiags(matrix, nr, nc):
    from collections import defaultdict
    d = defaultdict(list)
    for y in range(nr):
        for x in range(nc):
            d[x-y].append(matrix[y][x])
    return d

我们也可以从一个效用函数中获益，来呈现我们的结果

^{pr2}$

最后我们用IPython测试我们的东西

In [1]: def getdiags(matrix, nr, nc):
        from collections import defaultdict
        d = defaultdict(list)
        for y in range(nr):
                for x in range(nc):
                        d[x-y].append(matrix[y][x])
        return d
   ...:     

In [2]: def printdiags(diags):
        for i in sorted(diags):
                print diags[i]
   ...:         

In [3]: from pprint import pprint

In [4]: m = [["%3.3d"%(r*100+c)  for c in range(5)] for r in range(4)]

In [5]: pprint(m)
[['000', '001', '002', '003', '004'],
 ['100', '101', '102', '103', '104'],
 ['200', '201', '202', '203', '204'],
 ['300', '301', '302', '303', '304']]

In [6]: diags = getdiags(m, 4, 5)

In [7]: printdiags(diags)
['300']
['200', '301']
['100', '201', '302']
['000', '101', '202', '303']
['001', '102', '203', '304']
['002', '103', '204']
['003', '104']
['004']

In [8]: 

仅此

附录

在后期的编辑中，OP声明他们的输入是一个长度相等的字符串列表，并且根据对角线列表来寻找答案。在

上面我的getdiags也适用于新的替代数据结构，获得seeked列表非常简单：

def listofdiags(diags):
    return [''.join(diags[i]) for i in sorted(diags)]

当然，这种转换也可以在getdiagonals内部实现，但这只是一个练习。在

听着，不defaultdict

# List of Strings from Diagonals
def lsd(m, nr, nc):
    res = ["" for i in range(nr+nc-1)]
    for r in range(nr):
        for c in range(nc):
            i = c-r+nr-1
            res[i] = res[i]+m[r][c]
    return res

pprint(lsd(m, 4, 5))
# ['300',
#  '200301',
#  '100201302',
#  '000101202303',
#  '001102203304',
#  '002103204',
#  '003104',
#  '004']

yield解决方案

下面的方法效率较低，但为了完整起见，这里是：

def enumdiags(m, nr, nc):
    for i in range(nr+nc-1):
        s = ""
        for r in range(nr):
            for c in range(nc):
                if c-r+nr-1 == i : s = s+m[r][c]
        yield i, s

for i, s in enumdiags(m, 4, 5):
    print i, s
# 0 300
# 1 200301
# 2 100201302
# 3 000101202303
# 4 001102203304
# 5 002103204
# 6 003104
# 7 004

Answer 2

编辑以减少复杂性

    def printer(matrix, i, j, listOfDiagonals):
        if i + 1 > len(matrix) or j + 1 > len(matrix[0]):
            return listOfDiagonals
        else:
            listOfDiagonals.append(matrix[i][j])
            printer(matrix, i+1, j+1, listOfDiagonals)

    matrix = [[0 for i in range(10)] for j in range(10)]
    for i in matrix:
        print i
    list = []
    printer(matrix, 0, 0, list)
    print list

其中matrix是矩阵，i和{}是索引。在

这将递归地将索引位置的内容添加到列表中，当到达矩阵的边界时，该列表最终返回。这种设计的好处是矩阵不需要是正方形的，这样它就可以遍历对角线。在