我有一个N乘N的矩阵,只包含0和1,并且每列中必须只有一个“1”。对角线下方的元素必须为零(A[1][1]、A[2][1]、A[2][2]、A[3][1]、A[3][2]、A[3][3]=0)。例如:
A = [[1, 0, 0, 1], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]]
我需要存储这个矩阵的所有组合,保持前面给出的规则。我的想法是让第一行以所有的“1”开头,然后将最后一列中的“1”一次向下移动一个位置,直到它到达底部。然后,倒数第二列“1”将向下移动一个位置,最后一列“1”将重复其循环。所有可能的组合都是如此。你知道吗
抱歉,如果这是很难理解,但它类似于里程表时,最右边的表盘做了一个完整的旋转,第二到最右边的表盘转一个地方。唯一的区别是,在里程表中,每个表盘有10个值,在这种情况下,值的数量是不同的(由于对角线下方的值需要为零)。你知道吗
因为我不知道矩阵的大小,所以我不能使用一组嵌套的for循环,也不知道如何递归地实现这个程序。我也看过itertools.product
,但我不知道如何用它来处理对角线规则。任何帮助都将不胜感激,谢谢。你知道吗
不使用递归的尝试,其中N是矩阵宽度:
对于每一列,它创建一个包含所有可能的零序列和一个符合条件的序列的列表。然后将它们合并,得到按列列出的所有矩阵,从而计算每个矩阵的变换,从而得到结果。希望有帮助。你知道吗
这是我的解决方案。但是这不是一个快速的解决方案。它使用了搜索函数的递归实现。在每一次递归中,它探索每一行的所有可能乘积值(不包括当前行的第一个元素,直到对角线值),并检查当前解决方案是否有效。如果它到达递归的结尾,它将附加当前的矩阵解。你知道吗
假设是n!解决方案,但由于我在解决方案不正确时中断搜索,搜索在到达所有可能的解决方案之前停止。你知道吗
一个更有效的解决方案是搜索列,而不是搜索行,这是我现在搜索的方式,因为检查正确性需要更少的计算(只有当前列的总和正好为1时才需要检查)
当然,对列的搜索只需要沿着列移动1
相关问题 更多 >
编程相关推荐