尝试找出最长路径算法python

Question

我正在尝试制作一个python脚本，它让我在给定的矩阵（水平和垂直）中获得最长的重复字符。在

示例：

我有这个矩阵：

afaaf
rbaca
rlaff

给出这个矩阵作为输入，结果应该是：a3

你可以看到，矩阵的第3列，充满了a，而且，它也是矩阵中重复次数最多的字符。在

我拥有的：

^{pr2}$

这是我的源代码。 上面给出的例子也在源代码中使用。结果表明：r2这是错误的。。。同样，应该a3

它有4个功能：主、搜索、停止和检查点。在

• 主要是初始化程序
• search是我的递归函数，它接受一个参数（起始点），并且应该递归地检查最长的字符串。我有另一个矩阵，和原始矩阵一样长，只有1和0。1表示该职位已被访问，0表示没有。搜索功能是在搜索功能处理某个位置后，在右侧位置设置1。在
• stop正在检查matrix2是否满1，在本例中，矩阵都被解析了
• check_points接受2个参数、2个点列表，并返回这些点的最重复字符及其长度

什么不起作用：

大多数时候，结果都是给了我一个错误的字符，即使有时计数可能是正确的。有时它在水平方向上工作，有时它不工作。我确信我做错了什么，但是。。。我已经一个多星期没试着弄清楚怎么做了。在stackoverflow上又问了一个问题，说得更进一步了，但是。。。还是卡住了。在

如有任何建议，我们将不胜感激。在

Answer 1

您可以使用itertools.groupby快速查找某些字符的重复计数，使用izip_longest(*matrix)来转置矩阵（交换其行和列）。在

from itertools import groupby, izip_longest

matrix_string = """
afaaf
rbaca
rlaff
"""

def longest_repetition(row): 
    return max((sum(1 for item in group), letter) 
               for letter, group in groupby(row) 
               if letter is not None)

def main():
    matrix = [[letter for letter in row.strip()] 
              for row in matrix_string.strip().split('\n')]

    count, letter = max(
        max(longest_repetition(row) for row in matrix),
        max(longest_repetition(col) for col in izip_longest(*matrix))
    )

    print letter, count

if __name__ == '__main__':
    main()

由于您已经更新了需求，这里是代码的递归版本，并提供了一些解释。如果这不是一个任务，而这个任务是在现实生活中遇到的问题，那么您应该使用第一个版本。在

^{pr2}$

Answer 2

您也可以尝试使用collections.Counter(string).most_common()来获得最多的字符重复次数。在

from collections import Counter

string_matrix = """
afaaf
rbaca
rlaff
"""

def GetMostRepetitions(pos):
    mc = []

    for ii in range(pos[0],len(working_mat)):
        mc.extend(Counter(working_mat[ii]).most_common(1))  

        for jj in range(pos[1],len(working_mat[0])):
            column = []           

            for kk in range(ii,len(working_mat)):
                column.append(working_mat[kk][jj])

            mc.extend(Counter(column).most_common(1))          

    m = 0           
    for item in mc: 
        if item[1] > m:
            m = item[1]
            k = item[0]


    print(k, m)                 

working_mat = string_matrix.strip().split('\n')

for ii in range(len(working_mat)):
    for jj in range(len(working_mat[0])):
        pos = (ii,jj)
        GetMostRepetitions(pos)

正如Kolmar所说，您还可以使用更好的方法transpose the matrix。在