如何生成并遍历行、列均为0~n-1排列的n阶二维矩阵（拉丁方）

你要遍历的矩阵本质是n阶拉丁方，现有实现的核心问题有两个：一是主动把迭代器转为全量列表导致内存爆增，二是没有做剪枝，生成了大量不符合列约束的无效矩阵，浪费了大量计算资源。下面是对应优化方案：

方案1：最小修改仅解决内存问题 #

如果n非常小（≤4），可以不改核心逻辑，仅删除list()强制转换，直接使用itertools返回的迭代器逐次生成元素，不会全量加载到内存，生成后再校验列约束即可：

import itertools
n = 3
# 直接用迭代器，不转list
all_perms = itertools.permutations(range(n))
for matrix in itertools.product(all_perms, repeat=n):
    # 校验所有列是否为无重复排列
    if all(len(set(col)) == n for col in zip(*matrix)):
        # 在此处执行你的属性验证逻辑
        pass

该方案n≥5后运行效率会极低，因为99%以上生成的矩阵都不符合列约束。

方案2：回溯剪枝生成（推荐，支持n≤8场景） #

逐行构造矩阵，每新增一行时就校验列约束，直接过滤掉所有无效候选，计算量级直接等同于n阶拉丁方的总数量，比暴力枚举快几个数量级：

import itertools

def iterate_latin_squares(n):
    # 记录每一列已经出现过的元素，避免重复
    col_used = [set() for _ in range(n)]
    current_matrix = []

    def backtrack():
        if len(current_matrix) == n:
            # 返回符合要求的矩阵副本，避免回溯修改影响结果
            yield [list(row) for row in current_matrix]
            return
        # 遍历所有可能的行排列
        for perm in itertools.permutations(range(n)):
            # 预校验当前排列是否满足列无重复要求
            is_valid = True
            for col_idx, val in enumerate(perm):
                if val in col_used[col_idx]:
                    is_valid = False
                    break
            if not is_valid:
                continue
            # 状态更新
            current_matrix.append(perm)
            for col_idx, val in enumerate(perm):
                col_used[col_idx].add(val)
            # 递归生成下一行
            yield from backtrack()
            # 回溯恢复状态
            current_matrix.pop()
            for col_idx, val in enumerate(perm):
                col_used[col_idx].remove(val)
    
    yield from backtrack()

# 使用示例
n = 4
for matrix in iterate_latin_squares(n):
    # 在此处执行你的属性验证逻辑
    print(matrix)

可选优化：固定首行进一步提速 #

如果你的属性验证逻辑和行的顺序无关，或者不需要覆盖首行的所有排列情况，可以固定第一行为(0,1,2,...,n-1)，计算量直接降到原来的1/n!，n=8时可以提速4万倍以上，仅需要修改回溯的初始状态：

# 在backtrack调用前添加首行固定逻辑
first_row = tuple(range(n))
current_matrix.append(first_row)
for col_idx, val in enumerate(first_row):
    col_used[col_idx].add(val)
yield from backtrack()

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