二进制矩阵初始化算法

Question

我必须用 0 和 1 初始化一个矩阵（大小为 Nx（N-1）），每次我将 0（或 1）放在 [i， j] 位置时，矩阵中的 1（或 0）也会放在 [k， j] 位置，其中 k 是与 i 不同的随机行（请注意列是相同的）。

要满足的条件是同一行中不能有超过 2 个连续的 0 或 1。

因此，下一个矩阵将是无效的：

0 1 1

1

1 1

1

0 1

0 1 1

这个将是有效的：

0 1 1

1 0 0

1

1 0

0

0 1

关于如何实现此初始化的任何想法？假设矩阵以 -1 开头。

Answer 1

首先，要使这样的矩阵存在（每个 （i，j） 元组都有一个唯一的相反 （k，j） 元组），N 必须是 2 的倍数。

步骤 1 创建一个完全随机的 （N/2）*（N-1） 矩阵。

步骤 2 更正此矩阵中的错误，以便每一行都没有错误。使用以下算法：

for row in matrix:
    for i in range(0, len(row) - 2):
        if row[i] == row[i + 1] == row[i + 2]:
            row[i + 2] = 1 if row[i + 2] == 0 else 0 

步骤 3 对于每一行，按顺序（又名 N/2）附加反转行。

for row_index in range(N // 2):
    row = matrix[row_index]
    new_row = [0 if x == 1 else 1 for x in row]
    matrix.append(new_row)

步骤 4 对于每个 （i， j） 在 [0， N） 中生成一个 p，将 （i，j） 与 （p，j） 交换，看看它是否与行中的 3 模式相矛盾，如果是，请将它们交换回来。