3

各行と各列に正確に 1 つの要素があるように、nxn 行列を n 要素で埋めたいと思います。たとえば、3x3 マトリックスには、可能なソリューションとして次のようなものがあります。

1 0 0        0 1 0     0 0 1
0 1 0        1 0 0     1 0 0
0 0 1        0 0 1     0 1 0

以下は私が書いたコードです：

arr=[[0 for x in xrange(n)] for x in xrange(n)]
i=0
while i<n:
    j=0
    while j<n:
        arr[i][j]=0
        j+=1
    i+=1

i=0
while i<n:
    j=0
    while j<n:
        x=0
        while x<n:
            if((arr[i][x-1]==1) or (arr[x-1][j]==1)):
                break
            x+=1
        if(x==n-1 and arr[i][n-1]==0 and arr[n-1][j]==0):
            arr[i][j]=1
        j+=1
     i+=1

しかし、すべての要素はまだ0です。誰かが私の間違いを指摘してください。

4

3 に答える 3

8

各行と各列が正確に 1 つの要素を持つように、n 要素をもつ n*n 行列。

各行/列に 0以外の要素が1つだけある* n行列が必要だと思います

対角行列を構築する方法をお探しですか?

>>> n = 5
>>> [[1 if j == i else 0 for j in range(n)] for i in range(n)]
[[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]

可能なすべての順列が必要な場合は、次のように記述できます。

>>> n = 5
>>> m = [[1 if j == i else 0 for j in range(n)] for i in range(n)]
>>> from itertools import permutations
>>> for p in permutations(m):
>>>     print p
于 2013-08-03T23:28:22.863 に答える
3

あなたのコードに関して：

arr=[[0 for x in xrange(n)] for x in xrange(n)]

行列はすでに 0 に初期化されているため、次のループは冗長です。

i=0
while i<n:
    j=0
    while j<n:
        arr[i][j]=0
        j+=1
    i+=1

いくつかの変更がインライン化されました:

i=0
while i<n:
    j=0
    while j<n:
        ok = True
        x=0
        while x<n:
            # Why 'x-1' here?
            if((arr[i][x]==1) or (arr[x][j]==1)):
                ok = False
                break
            x+=1
        if ok:
            arr[i][j]=1
        j+=1
    i+=1
于 2013-08-03T23:49:46.733 に答える
2

この方法ですべてのマトリックスを生成できます。

for per in itertools.permutations(range(n)):
  matrix = [[0 for x in xrange(n)] for x in xrange(n)]
  for i, j in enumerate(per):
    matrix[i][j] = 1
  print matrix
于 2013-08-03T23:37:44.287 に答える