如何生成每行和为1、每列至少有赋值的n*m二进制矩阵（算法用）

前提条件 #

首先必须满足 n ≥ m，因为每列至少需要1个非零元素，而每行只能提供1个非零元素，总共有n个非零元素，要覆盖m列的话，n必须≥m。如果n < m，不存在这样的矩阵。

构造方法 #

方法1：基础固定分配法 #

• 先给前m行每一行分配唯一列：第i行（1≤i≤m）的第i列设为1，其余为0，这一步直接保证每列至少有一个1。
• 剩下的n-m行，每行任意选一列设为1（可重复选已有列），其余为0。

示例（n=5，m=3）：

1 0 0
0 1 0
0 0 1
1 0 0
0 1 0

方法2：随机生成法 #

如果需要随机生成符合要求的矩阵：

1. 先通过随机选择列，确保所有m列都被至少分配到一个行（用集合跟踪已覆盖的列）。
2. 剩下的行（若n>m）随机分配到任意列。
3. 对每行设置对应列的元素为1，其余为0。

伪代码实现：

# 初始化全0矩阵
matrix = [[0 for _ in range(m)] for _ in range(n)]

# 先确保每列至少有一个1
assigned_cols = set()
row_idx = 0
while len(assigned_cols) < m:
    col_idx = random.randint(0, m-1)
    matrix[row_idx][col_idx] = 1
    assigned_cols.add(col_idx)
    row_idx += 1

# 处理剩余行
for i in range(row_idx, n):
    col_idx = random.randint(0, m-1)
    matrix[i][col_idx] = 1

方法3：均匀分配法 #

如果希望各列的1的数量尽可能均匀：

• 计算每个列基础分配 k = n // m 个1，剩余 r = n % m 个列多分配1个1。
• 按顺序给每个列分配对应行数，将这些行的该列设为1。

示例（n=7，m=3）：k=2，r=1，第一列3个1，第二、三列各2个1：

1 0 0
1 0 0
1 0 0
0 1 0
0 1 0
0 0 1
0 0 1

验证方式 #

构造完成后可通过以下步骤验证：

• 遍历每行求和，确保每行和为1。
• 遍历每列求和，确保每列和≥1。

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