Python实现左序二进制矩阵列重排序：无行数上限场景解决方案问询

核心思路 #

不用将列显式转换为二进制整数，利用Python原生的元组逐元素比较规则，直接把每一列作为排序的key进行降序排列，完全不受行数N的上限限制。
元组比较的逻辑恰好符合二进制数的比较规则：优先比较第一个元素（对应矩阵第一行，最高有效位），相等再依次比较后续元素（对应更低的有效位）。

纯Python实现 #

def left_order_matrix(matrix):
    # 转置矩阵提取所有列，按列降序排序后再转置回行优先格式
    sorted_columns = sorted(zip(*matrix), reverse=True)
    return [list(row) for row in zip(*sorted_columns)]

# 示例测试
if __name__ == "__main__":
    matrix = [
        [0, 1, 1],
        [1, 1, 0]
    ]
    result = left_order_matrix(matrix)
    print(result)
    # 输出：[[1, 1, 0], [1, 0, 1]]

适用大规模矩阵的NumPy实现 #

如果处理的矩阵规模很大，推荐用NumPy版本，运算效率更高：

import numpy as np

def left_order_matrix_np(matrix):
    n_rows = matrix.shape[0]
    # lexsort默认最后传入的键优先级最高，倒序传入行实现最高位优先，最后反转得到降序结果
    sorted_col_indices = np.lexsort([matrix[i, :] for i in reversed(range(n_rows))])[::-1]
    return matrix[:, sorted_col_indices]

# 示例测试
if __name__ == "__main__":
    matrix = np.array([
        [0, 1, 1],
        [1, 1, 0]
    ])
    result = left_order_matrix_np(matrix)
    print(result)
    # 输出：
    # [[1 1 0]
    #  [1 0 1]]

方案优势 #

• 无行数限制：无需任何二进制转整数的计算，不会出现溢出、大数计算性能衰减的问题，哪怕行数达到十万级也可正常运行
• 时间复杂度最优：整体复杂度为O(KNlogK)（K为列数，N为行数），是该排序问题的理论最优复杂度
• 逻辑无偏差：完全匹配左序形式的定义，不会出现排序错误

内容的提问来源于stack exchange，提问作者Rylan Schaeffer