56 lines
1.5 KiB
Text
56 lines
1.5 KiB
Text
import "./fmt" for Fmt
|
|
import "./big" for BigInt
|
|
|
|
var permute // recursive
|
|
permute = Fn.new { |input|
|
|
if (input.count == 1) return [input]
|
|
var perms = []
|
|
var toInsert = input[0]
|
|
for (perm in permute.call(input[1..-1])) {
|
|
for (i in 0..perm.count) {
|
|
var newPerm = perm.toList
|
|
newPerm.insert(i, toInsert)
|
|
perms.add(newPerm)
|
|
}
|
|
}
|
|
return perms
|
|
}
|
|
|
|
var derange = Fn.new { |input|
|
|
if (input.isEmpty) return [input]
|
|
var perms = permute.call(input)
|
|
var derangements = []
|
|
for (perm in perms) {
|
|
var deranged = true
|
|
for (i in 0...perm.count) {
|
|
if (perm[i] == i) {
|
|
deranged = false
|
|
break
|
|
}
|
|
}
|
|
if (deranged) derangements.add(perm)
|
|
}
|
|
return derangements
|
|
}
|
|
|
|
var subFactorial // recursive
|
|
subFactorial = Fn.new { |n|
|
|
if (n == 0) return BigInt.one
|
|
if (n == 1) return BigInt.zero
|
|
return (subFactorial.call(n-1) + subFactorial.call(n-2)) * (n - 1)
|
|
}
|
|
|
|
var input = [0, 1, 2, 3]
|
|
var derangements = derange.call(input)
|
|
System.print("There are %(derangements.count) derangements of %(input), namely:\n")
|
|
System.print(derangements.join("\n"))
|
|
|
|
System.print("\nN Counted Calculated")
|
|
System.print("- ------- ----------")
|
|
for (n in 0..9) {
|
|
var list = List.filled(n, 0)
|
|
for (i in 0...n) list[i] = i
|
|
var counted = derange.call(list).count
|
|
Fmt.print("$d $-9d $-9i", n, counted, subFactorial.call(n))
|
|
}
|
|
System.print("\n!20 = %(subFactorial.call(20))")
|