72 lines
1.7 KiB
Go
72 lines
1.7 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"math/big"
|
|
)
|
|
|
|
// task 1: function returns list of derangements of n integers
|
|
func dList(n int) (r [][]int) {
|
|
a := make([]int, n)
|
|
for i := range a {
|
|
a[i] = i
|
|
}
|
|
// recursive closure permutes a
|
|
var recurse func(last int)
|
|
recurse = func(last int) {
|
|
if last == 0 {
|
|
// bottom of recursion. you get here once for each permutation.
|
|
// test if permutation is deranged.
|
|
for j, v := range a {
|
|
if j == v {
|
|
return // no, ignore it
|
|
}
|
|
}
|
|
// yes, save a copy
|
|
r = append(r, append([]int{}, a...))
|
|
return
|
|
}
|
|
for i := last; i >= 0; i-- {
|
|
a[i], a[last] = a[last], a[i]
|
|
recurse(last - 1)
|
|
a[i], a[last] = a[last], a[i]
|
|
}
|
|
}
|
|
recurse(n - 1)
|
|
return
|
|
}
|
|
|
|
// task 3: function computes subfactorial of n
|
|
func subFact(n int) *big.Int {
|
|
if n == 0 {
|
|
return big.NewInt(1)
|
|
} else if n == 1 {
|
|
return big.NewInt(0)
|
|
}
|
|
d0 := big.NewInt(1)
|
|
d1 := big.NewInt(0)
|
|
f := new(big.Int)
|
|
for i, n64 := int64(1), int64(n); i < n64; i++ {
|
|
d0, d1 = d1, d0.Mul(f.SetInt64(i), d0.Add(d0, d1))
|
|
}
|
|
return d1
|
|
}
|
|
|
|
func main() {
|
|
// task 2:
|
|
fmt.Println("Derangements of 4 integers")
|
|
for _, d := range dList(4) {
|
|
fmt.Println(d)
|
|
}
|
|
|
|
// task 4:
|
|
fmt.Println("\nNumber of derangements")
|
|
fmt.Println("N Counted Calculated")
|
|
for n := 0; n <= 9; n++ {
|
|
fmt.Printf("%d %8d %11s\n", n, len(dList(n)), subFact(n).String())
|
|
}
|
|
|
|
// stretch (sic)
|
|
fmt.Println("\n!20 =", subFact(20))
|
|
}
|