Permutations/Rank of a permutation: Difference between revisions
Permutations/Rank of a permutation (view source)
Revision as of 05:26, 9 December 2013
, 10 years agoGo solution
(Go solution) |
|||
Line 246:
6844249986266452118: [18, 20, 11, 19, 10, 12, 8, 9, 3, 13, 7, 15, 0, 1, 6, 5, 14, 17, 4, 16, 2] = 6844249986266452118
12804085840772788456: [8, 4, 14, 2, 5, 12, 19, 0, 9, 17, 11, 7, 16, 1, 20, 6, 10, 15, 18, 3, 13] = 12804085840772788456</pre>
=={{header|Go}}==
<lang go>package main
import (
"fmt"
"math/rand"
)
// returns permutation q of n items, using Myrvold-Ruskey rank.
func MRPerm(q, n int) []int {
p := ident(n)
var r int
for n > 0 {
q, r = q/n, q%n
n--
p[n], p[r] = p[r], p[n]
}
return p
}
// returns identity permutation of n items.
func ident(n int) []int {
p := make([]int, n)
for i := range p {
p[i] = i
}
return p
}
// returns Myrvold-Ruskey rank of permutation p
func MRRank(p []int) (r int) {
p = append([]int{}, p...)
inv := inverse(p)
for i := len(p) - 1; i > 0; i-- {
s := p[i]
p[inv[i]] = s
inv[s] = inv[i]
}
for i := 1; i < len(p); i++ {
r = r*(i+1) + p[i]
}
return
}
// returns inverse of a permutation.
func inverse(p []int) []int {
r := make([]int, len(p))
for i, x := range p {
r[x] = i
}
return r
}
// returns n!
func fact(n int) (f int) {
for f = n; n > 2; {
n--
f *= n
}
return
}
func main() {
n := 3
fmt.Println("permutations of", n, "items")
f := fact(n)
for i := 0; i < f; i++ {
p := MRPerm(i, n)
fmt.Println(i, p, MRRank(p))
}
n = 12
fmt.Println("permutations of", n, "items")
f = fact(n)
m := map[int]bool{}
for len(m) < 4 {
r := rand.Intn(f)
if m[r] {
continue
}
m[r] = true
fmt.Println(r, MRPerm(r, n))
}
}</lang>
{{out}}
<pre>
permutations of 3 items
0 [1 2 0] 0
1 [2 0 1] 1
2 [1 0 2] 2
3 [2 1 0] 3
4 [0 2 1] 4
5 [0 1 2] 5
permutations of 12 items
340494881 [4 2 3 9 0 8 10 11 1 6 7 5]
469128647 [7 6 10 5 2 3 1 0 8 4 9 11]
460982459 [4 9 5 7 0 8 6 10 2 1 3 11]
432900481 [0 6 5 10 8 2 4 7 3 9 11 1]
</pre>
=={{header|Haskell}}==
Line 291 ⟶ 390:
(23,[3,2,1,0],23)
</pre>
=={{header|J}}==
The J primitive <code>A.</code> provides an effective solution to this task. Generating 4 random permutations of 144 items takes about 6 milliseconds so solving the Stack Overflow question should be readily acheivable.
| |||