CODEWITHSUNDEEP
python
nish
nish

Reputation: 325

filling a n*n matrix with n elements

I want to fill a nxn matrix with n elements, such that each row and each column has exactly 1 element. E.g. a 3x3 matrix can have following as possible solutions:

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

Following is the code i wrote:

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

But all the elements are stiil 0. Could someone please point out my mistake.

Upvotes: 3

Views: 884

Answers (3)

Sylvain Leroux
Sylvain Leroux

Reputation: 52070

n*n matrix with n elements, such that each row and each column has exactly 1 element.

I assume you want a n*n matrix having exactly one non 0 element on each row/column

Are you looking for a way to build a diagonal matrix?

>>> 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]]

If you need all possible permutations, you could write:

>>> 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

Upvotes: 8

Sylvain Leroux
Sylvain Leroux

Reputation: 52070

Concerning your code:

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

The following loop is redundant since the matrix is already initialized to 0:

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

Some changes inline now:

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

Upvotes: 3

RiaD
RiaD

Reputation: 47658

You may generate all matricies this way:

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

Upvotes: 2

Related Questions