Factorial base numbers indexing permutations of a collection: Difference between revisions
Factorial base numbers indexing permutations of a collection (view source)
Revision as of 19:21, 9 December 2018
, 5 years agoAdded Go
m (→{{header|zkl}}: added some formatting) |
(Added Go) |
||
Line 127:
</pre>
8GB of memory is insufficient for rc's perm task
=={{header|Go}}==
<lang go>package main
import (
"fmt"
"math/rand"
"strconv"
"strings"
"time"
)
func factorial(n int) int {
fact := 1
for i := 2; i <= n; i++ {
fact *= i
}
return fact
}
func genFactBaseNums(size int, countOnly bool) ([][]int, int) {
var results [][]int
count := 0
for n := 0; ; n++ {
radix := 2
res := make([]int, size)
k := n
for k > 0 {
div := k / radix
rem := k % radix
if !countOnly {
if radix <= size+1 {
res[size-radix+1] = rem
}
}
k = div
radix++
}
if radix > size+2 {
break
}
count++
if !countOnly {
results = append(results, res)
}
}
return results, count
}
func mapToPerms(factNums [][]int) [][]int {
var perms [][]int
psize := len(factNums[0]) + 1
start := make([]int, psize)
for i := 0; i < psize; i++ {
start[i] = i
}
for _, fn := range factNums {
perm := make([]int, psize)
copy(perm, start)
for m := 0; m < len(fn); m++ {
g := fn[m]
if g == 0 {
continue
}
first := m
last := m + g
for i := 1; i <= g; i++ {
temp := perm[first]
for j := first + 1; j <= last; j++ {
perm[j-1] = perm[j]
}
perm[last] = temp
}
}
perms = append(perms, perm)
}
return perms
}
func join(is []int, sep string) string {
ss := make([]string, len(is))
for i := 0; i < len(is); i++ {
ss[i] = strconv.Itoa(is[i])
}
return strings.Join(ss, sep)
}
func undot(s string) []int {
ss := strings.Split(s, ".")
is := make([]int, len(ss))
for i := 0; i < len(ss); i++ {
is[i], _ = strconv.Atoi(ss[i])
}
return is
}
func main() {
rand.Seed(time.Now().UnixNano())
// Recreate the table.
factNums, _ := genFactBaseNums(3, false)
perms := mapToPerms(factNums)
for i, fn := range factNums {
fmt.Printf("%v -> %v\n", join(fn, "."), join(perms[i], ""))
}
// Check that the number of perms generated is equal to 11! (this takes a while).
_, count := genFactBaseNums(10, true)
fmt.Println("\nPermutations generated =", count)
fmt.Println("compared to 11! which =", factorial(11))
fmt.Println()
// Generate shuffles for the 2 given 51 digit factorial base numbers.
fbn51s := []string{
"39.49.7.47.29.30.2.12.10.3.29.37.33.17.12.31.29.34.17.25.2.4.25.4.1.14.20.6.21.18.1.1.1.4.0.5.15.12.4.3.10.10.9.1.6.5.5.3.0.0.0",
"51.48.16.22.3.0.19.34.29.1.36.30.12.32.12.29.30.26.14.21.8.12.1.3.10.4.7.17.6.21.8.12.15.15.13.15.7.3.12.11.9.5.5.6.6.3.4.0.3.2.1",
}
factNums = [][]int{undot(fbn51s[0]), undot(fbn51s[1])}
perms = mapToPerms(factNums)
shoe := []rune("A♠K♠Q♠J♠T♠9♠8♠7♠6♠5♠4♠3♠2♠A♥K♥Q♥J♥T♥9♥8♥7♥6♥5♥4♥3♥2♥A♦K♦Q♦J♦T♦9♦8♦7♦6♦5♦4♦3♦2♦A♣K♣Q♣J♣T♣9♣8♣7♣6♣5♣4♣3♣2♣")
cards := make([]string, 52)
for i := 0; i < 52; i++ {
cards[i] = string(shoe[2*i : 2*i+2])
if cards[i][0] == 'T' {
cards[i] = "10" + cards[i][1:]
}
}
for i, fbn51 := range fbn51s {
fmt.Println(fbn51)
for _, d := range perms[i] {
fmt.Print(cards[d])
}
fmt.Println("\n")
}
// Create a random 51 digit factorial base number and produce a shuffle from that.
fbn51 := make([]int, 51)
for i := 0; i < 51; i++ {
fbn51[i] = rand.Intn(52 - i)
}
fmt.Println(join(fbn51, "."))
perms = mapToPerms([][]int{fbn51})
for _, d := range perms[0] {
fmt.Print(cards[d])
}
fmt.Println()
}</lang>
{{out}}
Random for Part 4:
<pre>
0.0.0 -> 0123
0.0.1 -> 0132
0.1.0 -> 0213
0.1.1 -> 0231
0.2.0 -> 0312
0.2.1 -> 0321
1.0.0 -> 1023
1.0.1 -> 1032
1.1.0 -> 1203
1.1.1 -> 1230
1.2.0 -> 1302
1.2.1 -> 1320
2.0.0 -> 2013
2.0.1 -> 2031
2.1.0 -> 2103
2.1.1 -> 2130
2.2.0 -> 2301
2.2.1 -> 2310
3.0.0 -> 3012
3.0.1 -> 3021
3.1.0 -> 3102
3.1.1 -> 3120
3.2.0 -> 3201
3.2.1 -> 3210
Permutations generated = 39916800
compared to 11! which = 39916800
39.49.7.47.29.30.2.12.10.3.29.37.33.17.12.31.29.34.17.25.2.4.25.4.1.14.20.6.21.18.1.1.1.4.0.5.15.12.4.3.10.10.9.1.6.5.5.3.0.0.0
A♣3♣7♠4♣10♦8♦Q♠K♥2♠10♠4♦7♣J♣5♥10♥10♣K♣2♣3♥5♦J♠6♠Q♣5♠K♠A♦3♦Q♥8♣6♦9♠8♠4♠9♥A♠6♥5♣2♦7♥8♥9♣6♣7♦A♥J♦Q♦9♦2♥3♠J♥4♥K♦
51.48.16.22.3.0.19.34.29.1.36.30.12.32.12.29.30.26.14.21.8.12.1.3.10.4.7.17.6.21.8.12.15.15.13.15.7.3.12.11.9.5.5.6.6.3.4.0.3.2.1
2♣5♣J♥4♥J♠A♠5♥A♣6♦Q♠9♣3♦Q♥J♣10♥K♣10♣5♦7♥10♦3♠8♥10♠7♠6♥5♠K♥4♦A♥4♣2♥9♦Q♣8♣7♦6♣3♥6♠7♣2♦J♦9♥A♦Q♦8♦4♠K♦K♠3♣2♠8♠9♠
18.14.25.48.18.9.1.16.15.11.41.8.26.19.36.11.8.21.20.15.15.14.27.10.5.24.0.11.18.12.6.8.5.14.16.10.13.13.9.7.11.1.1.7.0.2.5.0.3.0.0
9♥K♥K♦2♣7♥5♠K♠6♥8♥A♥3♣4♠4♦J♦5♣J♥3♠6♦7♦A♦Q♦2♥7♣10♥8♠8♣A♠10♦Q♣8♦2♠4♥6♠J♣6♣3♦10♣9♣5♦3♥4♣J♠10♠A♣Q♠Q♥K♣9♠2♦7♠5♥9♦
</pre>
=={{header|Perl 6}}==
| |||