Python - 在矩阵中制作相同值的链表

Question

给定一些矩阵，我想创建一个包含一行中所有 1 的链表，然后检查是否有任何行中的任何指针，如果它们离开某个列i，它们指向同一个新列。例如，考虑这个图像：所有离开列 C3 的指针都指向同一个地方，它们自己。所有离开列 C1 的指针都指向同一个地方，列 C2，等等。但是离开 C5 的指针不指向同一列。我可以通过遍历每一行然后保存 1 的索引来创建一个链表。但是，我不确定如何创建一种有效的方法来检查离开特定列的箭头是否都指向同一位置。我可以遍历所有组合，但这将是非常低效的。我将如何进行？出于测试目的，这里是图片中的矩阵：matrix = [[1,1,0,0,0][0,0,1,0,0][1,1,0,1,0][0,0,1,0,1][0,0,1,1,0]]输入：矩阵 输出：“假，这个矩阵不满足要求” 输出解释：C5 指向 C1 和 C3。只有当列中的所有 1 都指向左侧的 EXACT 同一列时，矩阵才满足要求。因此，例如，如果 (E,C1) = 1 且 (E,C3) = 0，则此矩阵将满足要求。

Answer 1

制作集合列表，列表索引对应列，集合包含寻址列的索引。

扫描行时，添加链接列索引进行设置。最后检查设置长度。

您的情况示例（我使用列名而不是索引来避免错误）：

sets[C1] = {C2}

sets[C5] = {C1,C3}

速成代码：

matrix = [[1,1,0,0,0],[0,0,1,0,0],[1,1,0,1,0],[0,0,1,0,1],[0,0,1,1,0]]

sets = []

for col in range(len(matrix[0])):

    sets.append(set())

for row in range(len(matrix)):

    leftone = -1

    for col in range(len(matrix[row])):

        if matrix[row][col] == 1:

            if leftone < 0:

                sets[col].add(col)

            else:

                sets[col].add(leftone)

            leftone = col

for col in range(len(matrix[0])):

     print(sets[col], len(sets[col]) == 1)

>>>

{0} True

{0} True

{2} True

{1, 2} False

{2} True