Python - 2D 列表的里程表样式组合

Question

我有一个只包含零和一的 N×N 矩阵，每列中只能有一个"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"将重复其循环。这通过所有可能的组合继续。

抱歉，如果这很难理解，但它类似于里程表，当最右边的表盘旋转一圈时，最右边的第二个表盘会转动一个地方。唯一的区别是，在里程表中，每个刻度盘都有十个值，在这种情况下，值的数量会有所不同(由于对角线以下的值需要为零)。

因为我不知道矩阵的大小，所以我不能使用一定数量的嵌套 for 循环，我不确定如何递归实现这个程序。我也看过itertools.product但我不确定如何使用它来处理对角线规则。任何帮助将不胜感激，谢谢。

Answer 1

不使用递归的尝试，其中 N 是矩阵宽度：

import itertools
def column(index, length, size):
res = [0]* (length-1)
res.insert(index,1)
return res + [0]*(size - len(res))
N = 4
l = []
for i in range(1, N+1):
l1 = []
for j in range(0,i):
l1.append(column(j,i,N))
l.append(l1)
result = [list(x) for x in [zip(*r) for r in itertools.product(*l)]]

对于每一列，它都会创建一个包含每个可能的零序列的列表，以及一个尊重条件的列表。然后，它将它们组合在一起以获得按列列出的所有矩阵，以便计算每个矩阵的传输以获得结果。希望对您有所帮助。

Answer 2

这是我的解决方案。但是，这不是一个快速的解决方案。它使用搜索函数的递归实现。在每次递归时，它都会浏览每行的所有可能乘积值(不包括当前行的第一个元素，直到对角线值)，并检查当前解决方案是否有效。如果它到达递归的末尾，它将附加当前矩阵解。

假设它探索 n！ 解决方案，但由于我在解决方案不正确时中断搜索，因此搜索在到达所有可能的解决方案之前停止。

import sys, copy
from itertools import product

def recursiveSearch(actual, index, size, matrices):
if index==size-1:
for j in range(size):
if sum([actual[i][j] for i in range(size)])>1:
return
if sum([actual[i][j] for i in range(size) for j in range(size)]) == size:
matrices.append(actual)
return
return
cur_row = len(actual)
for j in range(size):
if sum([actual[i][j] for i in range(cur_row)])>1:
return
pr = product([0, 1], repeat=size-index-1)
for p in pr:
new_row = [0 for k in range(index+1)] + list(p)
new_matrix = copy.deepcopy(actual)
new_matrix.append(new_row)
recursiveSearch(new_matrix, index+1, size, matrices)

if __name__ == '__main__':
input_ = int(sys.argv[1])
pr = product([0,1], repeat=input_)
matrices = []
for p in pr:
recursiveSearch([list(p)], 0, input_, matrices)
for m in matrices:
print(m)

更有效的解决方案是搜索列，而不是我现在进行搜索的方式，因为检查正确性将需要更少的计算(仅当当前列的总和正好为 1 时才需要检查)

当然，搜索列需要沿列移动唯一的 1