<- previous index next ->
The "permanent" is similar to the "determinant" of a matrix
perm|a b| = ad + bc
|c d|
det|a b| = ad - bc
|c d|
perm|a b c| = aei + bfg + cdh + ceg + bdi + afh.
|d e f|
|g h i|
det|a b c| = aei + bfg + cdh - ceg - bdi - afh.
|d e f|
|g h i|
Notice the cyclic pattern. Clockwise is positive,
counter clockwise is negative.
The 3!=6 permutations of 1, 2, 3 with matrix subscripts are:
1 2 3 A(1,1) * A(2,2) * A(3,3) aei
2 3 1 A(1,2) * A(2,3) * A(3,1) bfg
3 1 2 A(1,3) * A(2,1) * A(3,2) cdh
3 2 1 A(1,3) * A(2,2) * A(3,1) ceg
2 1 3 A(1,2) * A(2,1) * A(3,3) bdi
1 3 2 A(1,1) * A(2,3) * A(3,2) afh
A(i,sigma(i))
Thus:
For a diagonal matrix, just one nonzero term,
the permanent is equal to the determinant.
Same for any square matrix with all zeros either
above or below the diagonal.
let sigma(n) represent all n! permutations of 1, 2, ..., n
,sigma(i) will be the ith element of the current permutation
perm of n by n matrix A with elements A(i,j) is
perm A = sum over sigma(n) product i=1..n A(i,sigma(i))
Direct computation requires n * n! floating point operations, flops.
Starting with the output file, permanent of random matrices
initializing, n= 1
A( 1 , 1 )= 0.79107778276832674
permanent = 0.79107778276832674 in 0.0000000000000000 seconds
initializing, n= 2
A( 1 , 1 )= 0.64429498726702061
A( 1 , 2 )= 0.66585099681553006
A( 2 , 1 )= 0.95770347861466165
A( 2 , 2 )= 0.12236507661750777
permanent = 0.71652702137047830 in 0.0000000000000000 seconds
initializing, n= 3
A( 1 , 1 )= 0.58984271045301240
A( 1 , 2 )= 0.48643458377869547
A( 1 , 3 )= 0.50604956853485183
A( 2 , 1 )= 0.17509836525428032
A( 2 , 2 )= 0.87822482868946383
A( 2 , 3 )= 0.32469578381846464
A( 3 , 1 )= 0.16203863693496148
A( 3 , 2 )= 0.38337096589774405
A( 3 , 3 )= 0.31582384338407954
permanent = 0.39550116362032195 in 0.0000000000000000 seconds
initializing, n= 4
permanent = 1.6972004238748366 in 0.0000000000000000 seconds
initializing, n= 5
permanent = 1.1995565139206676 in 0.0000000000000000 seconds
initializing, n= 6
permanent = 8.9015066849645361 in 0.0000000000000000 seconds
initializing, n= 7
permanent = 17.050252850698129 in 1.99999997857958078E-003 seconds
initializing, n= 8
permanent = 178.10765667301948 in 1.30000000353902578E-002 seconds
initializing, n= 9
permanent = 516.72987129756325 in 8.60000000102445483E-002 seconds
initializing, n= 10
permanent = 1020.0838023705367 in 0.68199999991338700 seconds
initializing, n= 11
permanent = 19478.337547346702 in 8.0130000000353903 seconds
initializing, n= 12
permanent = 57979.479713982662 in 102.07500000006985 seconds
flops are n * n!
finished test_permanent.f90
test_permanent_f90.out output
test_permanent.f90 source code
permanent.f90 compute permanent source code
permute.f90 compute permutations source code
test_permute.f90 test permute source code
test_permute_f90.out output
udrnrt.f90 compute random numbers source code
makefile.permanent for above/a>
Compute Combinations and Permutations in other languages
combinations.c "C" source code
combinations.h header file
combinations.adb Ada source code
combinations.ads specification
combinations.java Java source code
permute.c "C" source code
permute.h header file
test_permute.c "C" source code
test_permute_c.out output
permute.adb Ada source code
permute.ads specification
test_permute.adb Ada source code
test_permute_ada.out output
permute.java Java source code
test_permute.java Java source code
test_permute_java.out output
<- previous index next ->