CODEWITHSUNDEEP
pythonarraysmatrixpermutation
Patrick Lewis
Patrick Lewis

Reputation: 93

Generating permutation matrices of a 2 dimensional array in Python

I am wanting to generate all the square permutation matrices for an input d (which is a prime number). I know there are examples on how to do this for all permutations in general, but I am looking for permutation matrices which satisfy the mathematical definition;

A permutation matrix is a matrix obtained by permuting the rows of an dxd identity matrix according to some permutation of the numbers 1 to d. Every row and column therefore contains precisely a single 1 with 0s everywhere else.

e.g for 2x2, [[1,0],[0,1]] and [[0,1],[1,0]] satisfy this, while [[1,1],[0,0]], etc... do not, so I am hoping this isn't a duplicate question. I have a code which does this and my test is that I should have d! matrices. When I get to 11, I should get 11! matrices but I get the error that my code is shutting down due to memory loss. I am hoping someone has a more efficient way of solving this problem as I would like to go to larger prime numbers;

import math
import numpy as np
import cmath
from sympy.utilities.iterables import multiset_permutations
from itertools import permutations, chain
from pprint import pprint
from numpy import ndarray
from numpy import linalg as LA


d=5
print("Prime dimension",d)
a=[1]+[0 for _ in range(d-1)]
N=[] 
P=[]
Pdagger=[]
for p in multiset_permutations(a):
    N.append(p)

#Generate a list of ALL the permutation matrices including Identity (last)
for n in multiset_permutations(N):
    n
    P.append(n)
print(len(P))

I am running my code in an IPython Jupyter notebook if that helps. I understand this may not be the best/most efficient way to run this but I'm looking for any advice anyone can give me. All the libraries imported at the top are relevant to the code later on.

Upvotes: 2

Views: 12604

Answers (1)

John Coleman
John Coleman

Reputation: 51998

Too large for a comment. Here is the sort of thing that I had in mind:

import itertools

def I(n):
    A = []
    for i in range(n):
        A.append([1 if j == i else 0 for j in range(n)])
    return A

#tests:

A = I(3)

for m in itertools.permutations(A):
    print('\n'.join(str(row) for row in m))
    print('')

A = I(11)
count = 0
for m in itertools.permutations(A):
    count = count + m[0][0] #for testing purposes
print(count)

Output:

[1, 0, 0]
[0, 1, 0]
[0, 0, 1]

[1, 0, 0]
[0, 0, 1]
[0, 1, 0]

[0, 1, 0]
[1, 0, 0]
[0, 0, 1]

[0, 1, 0]
[0, 0, 1]
[1, 0, 0]

[0, 0, 1]
[1, 0, 0]
[0, 1, 0]

[0, 0, 1]
[0, 1, 0]
[1, 0, 0]

3628800

This take about 10 seconds to run and the final number is 11!/11 (which makes sense).

Upvotes: 6

Related Questions