生成全量n阶Permutation matrices（置换矩阵）的实现方法咨询

首先明确核心对应逻辑：n阶置换矩阵与n个元素的全排列一一对应，只需先生成所有全排列，再将排列转换为对应矩阵即可。例如3阶排列[0,1,2]（索引从0开始）就对应你给出的单位矩阵样例；若排列为[1,0,2]，则第一行的1位于第1列，第二行的1位于第0列，第三行的1位于第2列，对应交换前两行的置换矩阵。

你之前提到的交换初始单位矩阵行的方法本身是可行的，没有覆盖所有情况大概率是交换逻辑没有遍历完所有行的排列组合，本质和生成全排列的逻辑一致。

方案1：调用内置全排列工具实现（最快落地） #

绝大多数编程语言的标准库都提供全排列生成接口，只需补充排列转矩阵的逻辑即可，Python示例如下：

import itertools

def generate_permutation_matrices(n):
    matrices = []
    # 生成0~n-1的所有全排列
    for perm in itertools.permutations(range(n)):
        # 初始化n阶全0矩阵
        mat = [[0]*n for _ in range(n)]
        for row_idx, col_idx in enumerate(perm):
            mat[row_idx][col_idx] = 1
        matrices.append(mat)
    return matrices

该方案无需自行实现排列逻辑，出错概率极低，适合快速落地。

方案2：手动递归/回溯实现 #

如果需要自行实现递归逻辑，无需依赖第三方库，可以用回溯法逐行确定1的位置，天然保证每行每列仅存在一个1：

• 递归终止条件：已处理完所有n行，将当前构造的矩阵存入结果集
• 递归过程：处理第k行时，遍历所有未被使用的列，将当前行的对应列设为1，标记该列已使用，进入下一行的递归；递归返回后做回溯操作，将对应位置改回0，取消列的使用标记

对应Python实现示例：

def generate_permutation_matrices_recursive(n):
    result = []
    used_cols = [False] * n
    current_mat = [[0]*n for _ in range(n)]

    def backtrack(row):
        if row == n:
            # 深拷贝当前矩阵加入结果
            result.append([r.copy() for r in current_mat])
            return
        for col in range(n):
            if not used_cols[col]:
                # 选中当前列
                current_mat[row][col] = 1
                used_cols[col] = True
                # 处理下一行
                backtrack(row + 1)
                # 回溯重置状态
                current_mat[row][col] = 0
                used_cols[col] = False
    
    backtrack(0)
    return result

该逻辑不会出现重复或遗漏的情况，且容易调试。

注意事项 #

n阶置换矩阵总共有n!个，n≥10时数量就会超过360万，n≥12时数量达到4.79亿，会占用极高的内存和运算资源，注意控制n的取值规模。

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