Python里程表样式的2D Lis组合

2024-03-29 06:17:40 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个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,但我不知道如何用它来处理对角线规则。任何帮助都将不胜感激,谢谢。你知道吗


Tags: 程序元素for数量规则地方情况矩阵
2条回答

不使用递归的尝试,其中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)]]

对于每一列,它创建一个包含所有可能的零序列和一个符合条件的序列的列表。然后将它们合并,得到按列列出的所有矩阵,从而计算每个矩阵的变换,从而得到结果。希望有帮助。你知道吗

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

假设是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

相关问题 更多 >