Index finite lists of positive integers: Difference between revisions
Content added Content deleted
(→{{header|Go}}: cleanups. handle empty list, return errors rather than panic, add output showing empty list and errors.) |
(→{{header|Go}}: add bijective solution) |
||
| Line 48: | Line 48: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
'''Bijective''' |
|||
A list element n is encoded as a 1 followed by n 0's. Element encodings are concatenated to form a single integer rank. An advantage of this encoding is that no special case is required to handle the empty list. |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"math/big" |
|||
) |
|||
func rank(l []uint) (r big.Int) { |
|||
for _, n := range l { |
|||
r.Lsh(&r, n+1) |
|||
r.SetBit(&r, int(n), 1) |
|||
} |
|||
return |
|||
} |
|||
func unrank(n big.Int) (l []uint) { |
|||
m := new(big.Int).Set(&n) |
|||
for a := m.BitLen(); a > 0; { |
|||
m.SetBit(m, a-1, 0) |
|||
b := m.BitLen() |
|||
l = append(l, uint(a-b-1)) |
|||
a = b |
|||
} |
|||
return |
|||
} |
|||
func main() { |
|||
var b big.Int |
|||
for i := 0; i <= 10; i++ { |
|||
b.SetInt64(int64(i)) |
|||
u := unrank(b) |
|||
r := rank(u) |
|||
fmt.Println(i, u, &r) |
|||
} |
|||
b.SetString("12345678901234567890", 10) |
|||
u := unrank(b) |
|||
r := rank(u) |
|||
fmt.Printf("\n%v\n%d\n%d\n", &b, u, &r) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
0 [] 0 |
|||
1 [0] 1 |
|||
2 [1] 2 |
|||
3 [0 0] 3 |
|||
4 [2] 4 |
|||
5 [1 0] 5 |
|||
6 [0 1] 6 |
|||
7 [0 0 0] 7 |
|||
8 [3] 8 |
|||
9 [2 0] 9 |
|||
10 [1 1] 10 |
|||
12345678901234567890 |
|||
[1 1 1 0 1 1 1 2 1 1 2 0 3 0 2 0 0 1 1 0 3 0 0 0 0 4 1 1 0 1 2 1] |
|||
12345678901234567890 |
|||
</pre> |
|||
'''Alternative''' |
|||
A bit of a hack to make a base 11 number then interpret it as base 16, just because that's easiest. Not bijective. Practical though for small lists of large numbers. |
|||
<lang go>package main |
<lang go>package main |
||