#perm01.py
'''
Compute the permanent of a 0-1 matrix
'''

import numpy as np
from math import factorial

def minor(M, i, j):
    return np.delete(np.delete(M,i,axis=0), j, axis=1)

def perm(M):
    size = M.shape[0]
    colsums = sum(M)
    rowsums = sum(M.transpose())
    c = np.argmin(colsums)
    r = np.argmin(rowsums)
    answer = 0
    if colsums[c] <= rowsums[r]:
        if colsums[c] == size:
            return factorial(size)
        for k in range(size):
            if M[k, c] == 1:
                answer += perm(minor(M,k,c))
    else:
        for k in range(size):
            if M[r, k] == 1:
                answer += perm(minor(M,r,k))
    return answer

if __name__=='__main__':
    M = np.zeros((7,7), dtype=np.int)
    for k in range(7):
        M[k,k]=M[k,(k+1)%7]=M[k,(k-1)%7]=1
    M = np.ones((7,7), dtype=int)-M
    print(perm(M))