How to resolve the algorithm Index finite lists of positive integers step by step in the Go programming language

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm Index finite lists of positive integers step by step in the Go programming language

Table of Contents

Problem Statement

It is known that the set of finite lists of positive integers is   countable.
This means that there exists a subset of natural integers which can be mapped to the set of finite lists of positive integers.

Implement such a mapping:

Demonstrate your solution by:

There are many ways to do this.   Feel free to choose any one you like.

Make the   rank   function as a   bijection   and show   unrank(n)   for   n   varying from   0   to   10.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Index finite lists of positive integers step by step in the Go programming language

Explanation of the First Source Code:

This code showcases the ranking and unranking of permutations using the Go programming language. Permutations are ordered sequences of unique elements from a set. Here's how it works:

  1. rank Function:

    • Takes a list of integers l as input.
    • Creates a big integer r.
    • Iterates through each integer n in l.
    • Left-shifts r by n+1 bits (multiply r by 2^(n+1)).
    • Sets the bit at position n in r to 1.
    • Returns the resulting r.

  2. unrank Function:

    • Takes a big integer n as input.
    • Creates a new big integer m by copying n.
    • While m has bits set:
      • Clears the rightmost set bit in m.
      • Stores the number of cleared bits in a.
      • Appends a-b-1 to the list l, where b is the number of bits remaining set in m.
    • Returns the list l.

  3. main Function:

    • Demonstrates the rank and unrank functions.
    • Generates a series of big integers, ranks them using rank, and unranks the results using unrank.
    • Prints the original integers, their ranks, and the unranked values.

Explanation of the Second Source Code:

This code also demonstrates ranking and unranking, but it uses different techniques to handle negative integers and ensure bijectivity (the property that a function has an inverse that returns the original input).

  1. rank Function:

    • Takes a list of big integers l as input.
    • Converts each integer to a base 16 string by prepending "a" (since base 11 is not convenient in big.Int).
    • Joins the strings and creates a big integer r from the result.
    • Handles negative integers by returning an error.

  2. unrank Function:

    • Takes a big integer r as input.
    • Converts r to a base 16 string s16.
    • Splits s16 at "a" to recover the base 10 numbers.
    • Creates a list of big integers l and parses the recovered numbers.
    • Handles non-bijectivity by returning an error if the parsing fails.

  3. main Function:

    • Demonstrates the rank and unrank functions.
    • Generates a random list of positive integers, ranks it, and unranks the result.
    • Prints the original list, its rank, and the unranked values.
    • Also shows error handling for negative integers and demonstrates non-bijectivity.

  4. random Function:

    • Generates a random list of big integers in the range [1, 2^100] using random numbers.

Source code in the go programming language

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)
}


package main

import (
    "fmt"
    "math/big"
    "math/rand"
    "strings"
    "time"
)

// 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.
func rank(l []big.Int) (r big.Int, err error) {
    if len(l) == 0 {
        return
    }
    s := make([]string, len(l))
    for i, n := range l {
        ns := n.String()
        if ns[0] == '-' {
            return r, fmt.Errorf("negative integers not mapped")
        }
        s[i] = "a" + ns
    }
    r.SetString(strings.Join(s, ""), 16)
    return
}

// Split the base 16 representation at "a", recover the base 10 numbers.
func unrank(r big.Int) ([]big.Int, error) {
    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))
    for i, s1 := range s {
        if _, ok := l[i].SetString(s1, 10); !ok {
            return nil, fmt.Errorf("unrank not bijective")
        }
    }
    return l, nil
}

func main() {
    // show empty list
    var l []big.Int
    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 {
        fmt.Println("  ", &n)
    }
    fmt.Println("Rank:")
    fmt.Println("  ", &r)
    fmt.Println("Unranked:")
    for _, n := range u {
        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 0 to 5 numbers in the range 1 to 2^100
func random() []big.Int {
    r := rand.New(rand.NewSource(time.Now().Unix()))
    l := make([]big.Int, r.Intn(6))
    one := big.NewInt(1)
    max := new(big.Int).Lsh(one, 100)
    for i := range l {
        l[i].Add(one, l[i].Rand(r, max))
    }
    return l
}

You may also check:How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the C++ programming language
You may also check:How to resolve the algorithm Arrays step by step in the Simula programming language
You may also check:How to resolve the algorithm RIPEMD-160 step by step in the Factor programming language
You may also check:How to resolve the algorithm Sum digits of an integer step by step in the Python programming language
You may also check:How to resolve the algorithm Symmetric difference step by step in the PL/I programming language