88 lines
2.1 KiB
Plaintext
88 lines
2.1 KiB
Plaintext
// version 1.1.2
|
|
|
|
typealias Matrix = Array<DoubleArray>
|
|
|
|
fun johnsonTrotter(n: Int): Pair<List<IntArray>, List<Int>> {
|
|
val p = IntArray(n) { it } // permutation
|
|
val q = IntArray(n) { it } // inverse permutation
|
|
val d = IntArray(n) { -1 } // direction = 1 or -1
|
|
var sign = 1
|
|
val perms = mutableListOf<IntArray>()
|
|
val signs = mutableListOf<Int>()
|
|
|
|
fun permute(k: Int) {
|
|
if (k >= n) {
|
|
perms.add(p.copyOf())
|
|
signs.add(sign)
|
|
sign *= -1
|
|
return
|
|
}
|
|
permute(k + 1)
|
|
for (i in 0 until k) {
|
|
val z = p[q[k] + d[k]]
|
|
p[q[k]] = z
|
|
p[q[k] + d[k]] = k
|
|
q[z] = q[k]
|
|
q[k] += d[k]
|
|
permute(k + 1)
|
|
}
|
|
d[k] *= -1
|
|
}
|
|
|
|
permute(0)
|
|
return perms to signs
|
|
}
|
|
|
|
fun determinant(m: Matrix): Double {
|
|
val (sigmas, signs) = johnsonTrotter(m.size)
|
|
var sum = 0.0
|
|
for ((i, sigma) in sigmas.withIndex()) {
|
|
var prod = 1.0
|
|
for ((j, s) in sigma.withIndex()) prod *= m[j][s]
|
|
sum += signs[i] * prod
|
|
}
|
|
return sum
|
|
}
|
|
|
|
fun permanent(m: Matrix) : Double {
|
|
val (sigmas, _) = johnsonTrotter(m.size)
|
|
var sum = 0.0
|
|
for (sigma in sigmas) {
|
|
var prod = 1.0
|
|
for ((i, s) in sigma.withIndex()) prod *= m[i][s]
|
|
sum += prod
|
|
}
|
|
return sum
|
|
}
|
|
|
|
fun main(args: Array<String>) {
|
|
val m1 = arrayOf(
|
|
doubleArrayOf(1.0)
|
|
)
|
|
|
|
val m2 = arrayOf(
|
|
doubleArrayOf(1.0, 2.0),
|
|
doubleArrayOf(3.0, 4.0)
|
|
)
|
|
|
|
val m3 = arrayOf(
|
|
doubleArrayOf(2.0, 9.0, 4.0),
|
|
doubleArrayOf(7.0, 5.0, 3.0),
|
|
doubleArrayOf(6.0, 1.0, 8.0)
|
|
)
|
|
|
|
val m4 = arrayOf(
|
|
doubleArrayOf( 1.0, 2.0, 3.0, 4.0),
|
|
doubleArrayOf( 4.0, 5.0, 6.0, 7.0),
|
|
doubleArrayOf( 7.0, 8.0, 9.0, 10.0),
|
|
doubleArrayOf(10.0, 11.0, 12.0, 13.0)
|
|
)
|
|
|
|
val matrices = arrayOf(m1, m2, m3, m4)
|
|
for (m in matrices) {
|
|
println("m${m.size} -> ")
|
|
println(" determinant = ${determinant(m)}")
|
|
println(" permanent = ${permanent(m)}\n")
|
|
}
|
|
}
|