Skip to main content
 首页 » 编程设计

python之如何找到值按行和列排序的最大子矩阵

2025年01月19日13jpfss

给定一个矩阵,例如:

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

...如何找到所有行都排序且所有列都排序的最大子矩阵(即具有最多值)?

在上面的例子中,解是 (1,0)-(2,3) 处的子矩阵:

  1 4 6 8      
  3 6 7 9 

它的大小是 8。

请您参考如下方法:

您可以使用递归来获得适合给定行段下方的最大化区域,该行段本身已被验证为非递减值序列。找到的区域将保证在给定行段的列范围内,但可以更窄并跨越给定行下方的几行。

返回的区域可以向上扩展一行,宽度为该区域已有的宽度。如果该段不能更宽,那么我们将找到可以由该段(或完整段)的子序列与其下方的行组合而成的最大面积。

通过从为所有行的所有段检索的结果中筛选出最佳结果,我们将找到解决方案。

为了避免重复已经对完全相同的段进行的递归计算,可以使用内存(直接编程)。

这里是建议的代码:

from collections import namedtuple 
Area = namedtuple('Area', 'start_row_num start_col_num end_row_num end_col_num size') 
EMPTY_AREA = Area(0,0,0,0,0) 
 
def greatest_sub(matrix): 
    memo = {} 
 
    # Function that will be called recursively 
    def greatest_downward_extension(row_num, start_col_num, end_col_num, depth=0): 
        # Exit if the described segment has no width 
        if end_col_num <= start_col_num: 
            return EMPTY_AREA 
        next_row_num = row_num + 1 
        # Use memoisation: 
        #   Derive an ID (hash) from the segment's attributes for use as memoisation key 
        segment_id = ((row_num * len(matrix[0]) + start_col_num)  
                      * len(matrix[0]) + end_col_num) 
        if segment_id in memo: 
            return memo[segment_id] 
        # This segment without additional rows is currently the best we have: 
        best = Area(row_num, start_col_num, next_row_num, end_col_num, 
                    end_col_num - start_col_num) 
        if next_row_num >= len(matrix): 
            return best 
        next_row = matrix[next_row_num] 
        row = matrix[row_num] 
        prev_val = -float('inf') 
        for col_num in range(start_col_num, end_col_num + 1): 
            # Detect interruption in increasing series,  
            #    either vertically (1) or horizontally (0) 
            status = (1 if col_num >= end_col_num or next_row[col_num] < row[col_num] 
                    else (0 if next_row[col_num] < prev_val 
                    else -1)) 
            if status >= 0: # There is an interruption: stop segment 
                # Find largest area below current row segment, within its column range 
                result = greatest_downward_extension(next_row_num, 
                                                     start_col_num, col_num) 
                # Get column range of found area and add that range from the current row 
                size = result.size + result.end_col_num - result.start_col_num 
                if size > best.size: 
                    best = Area(row_num, result.start_col_num,  
                                result.end_row_num, result.end_col_num, size) 
                if col_num >= end_col_num: 
                    break 
                # When the interruption was vertical, the next segment can only start 
                #    at the next column (status == 1) 
                start_col_num = col_num + status 
            prev_val = row[col_num] 
        memo[segment_id] = best 
        return best 
 
    # For each row identify the segments with non-decreasing values 
    best = EMPTY_AREA 
    for row_num, row in enumerate(matrix): 
        prev_val = -float('inf') 
        start_col_num = 0 
        for end_col_num in range(start_col_num, len(row) + 1): 
            # When value decreases (or we reached the end of the row),  
            #   the segment ends here 
            if end_col_num >= len(row) or row[end_col_num] < prev_val: 
                # Find largest area below current row segment, within its column range 
                result = greatest_downward_extension(row_num, start_col_num, end_col_num) 
                if result.size > best.size: 
                    best = result 
                if end_col_num >= len(row): 
                    break 
                start_col_num = end_col_num 
            prev_val = row[end_col_num] 
    return best 
 
# Sample call     
matrix = [ 
    [2, 5, 3, 8, 3], 
    [1, 4, 6, 8, 4], 
    [3, 6, 7, 9, 5], 
    [1, 3, 6, 4, 2], 
    [2, 6, 4, 3, 1]] 
 
result = greatest_sub(matrix) 
print(result) 

示例数据的输出将是:

Area(start_row_num=1, start_col_num=0, end_row_num=3, end_col_num=4, size=8)