Factorial base numbers indexing permutations of a collection: Difference between revisions
Content deleted Content added
m →{{header|zkl}}: added some formatting |
Added Go |
||
Line 127: | Line 127: | ||
</pre> |
</pre> |
||
8GB of memory is insufficient for rc's perm task |
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}}== |
=={{header|Perl 6}}== |