Index finite lists of positive integers: Difference between revisions

Content added Content deleted
m (fixed an HTML tag.)
(→‎{{header|Go}}: cleanups. handle empty list, return errors rather than panic, add output showing empty list and errors.)
Line 58: Line 58:
)
)


// Join base 10 representations with an "a" and you get a base 11 number.
// Prepend base 10 representation with an "a" and you get a base 11 number.
// Unfortunately base 11 is a little awkward with big.Int, so just treat it as base 16.
// Unfortunately base 11 is a little awkward with big.Int, so just treat it
// as base 16.
func rank(l []big.Int) *big.Int {
func rank(l []big.Int) (r big.Int, err error) {
if len(l) == 0 {
⚫
return
⚫
}
s := make([]string, len(l))
s := make([]string, len(l))
for i, n := range l {
for i, n := range l {
s[i] = n.String()
ns := n.String()
if ns[0] == '-' {
⚫
}
return r, fmt.Errorf("negative integers not mapped")
⚫
i, ok := new(big.Int).SetString(strings.Join(s, "a"), 16)
if !ok {
}
panic("huh")
s[i] = "a" + ns
}
}
⚫
r.SetString(strings.Join(s, ""), 16)
return i
return
}
}


// Split the base 16 representation at "a", recover the base 10 numbers.
// Split the base 16 representation at "a", recover the base 10 numbers.
func unrank(r *big.Int) []big.Int {
func unrank(r big.Int) ([]big.Int, error) {
s := strings.Split(fmt.Sprintf("%x", r), "a")
s16 := fmt.Sprintf("%x", &r)
switch {
case s16 == "0":
return nil, nil // empty list
case s16[0] != 'a':
return nil, fmt.Errorf("unrank not bijective")
}
s := strings.Split(s16[1:], "a")
l := make([]big.Int, len(s))
l := make([]big.Int, len(s))
for i, s1 := range s {
for i, s1 := range s {
_, ok := l[i].SetString(s1, 10)
if _, ok := l[i].SetString(s1, 10); !ok {
return nil, fmt.Errorf("unrank not bijective")
⚫
if !ok {
panic("really")
}
}
}
}
return l
return l, nil
}
}


func main() {
func main() {
l := random()
// show empty list
var l []big.Int
⚫
fmt.Println("List:")
⚫
r, _ := rank(l)
⚫
u, _ := unrank(r)
fmt.Println("Empty list:", l, &r, u)

// show random list
l = random()
r, _ = rank(l)
u, _ = unrank(r)
⚫
fmt.Println("\nList:")
for _, n := range l {
for _, n := range l {
fmt.Println(" ", &n)
fmt.Println(" ", &n)
}
}
⚫
r := rank(l)
fmt.Println("Rank:")
fmt.Println("Rank:")
fmt.Println(" ", r)
fmt.Println(" ", &r)
⚫
u := unrank(r)
fmt.Println("Unranked:")
fmt.Println("Unranked:")
for _, n := range u {
for _, n := range u {
fmt.Println(" ", &n)
fmt.Println(" ", &n)
}
}

// show error with list containing negative
var n big.Int
n.SetInt64(-5)
_, err := rank([]big.Int{n})
fmt.Println("\nList element:", &n, err)

// show technique is not bijective
n.SetInt64(1)
_, err = unrank(n)
fmt.Println("Rank:", &n, err)
}
}


// returns 3 to 10 numbers in the range 1 to 2^100
// returns 0 to 5 numbers in the range 1 to 2^100
func random() []big.Int {
func random() []big.Int {
r := rand.New(rand.NewSource(time.Now().Unix()))
r := rand.New(rand.NewSource(time.Now().Unix()))
l := make([]big.Int, 3+r.Intn(8))
l := make([]big.Int, r.Intn(6))
one := big.NewInt(1)
one := big.NewInt(1)
max := new(big.Int).Lsh(one, 100)
max := new(big.Int).Lsh(one, 100)
Line 114: Line 143:
{{out}}
{{out}}
<pre>
<pre>
Empty list: [] 0 []

List:
List:
170245492534662309353778826165
250046378143152073779399139308
82227712638678862510272817700
433677733115839140356036818773
709681404405498840918712626000
Rank:
Rank:
17827272030291729487097780664374477811820701746650470453292650775464474368
86898591846547743089837040293705765764160568618712035006919317223922729203294339688481288514295259746298650624
Unranked:
Unranked:
170245492534662309353778826165
250046378143152073779399139308
82227712638678862510272817700
433677733115839140356036818773

709681404405498840918712626000
List element: -5 negative integers not handled
Rank: 1 unrank not bijective
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Index_finite_lists_of_positive_integers"