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.



Task

Implement such a mapping:

   write a function     rank     which assigns an integer to any finite, arbitrarily long list of arbitrary large positive integers.
   write a function   unrank   which is the   rank    inverse function.


Demonstrate your solution by:

   picking a random-length list of random positive integers
   turn it into an integer,   and 
   get the list back.


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



Extra credit

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




type duple
    A as ulongint
    B as ulongint
end type
 
function two_to_one( A as ulongint, B as ulongint ) as ulongint   'converts two numbers into one
    dim as uinteger ret = A*A + B*B + 2*A*B - 3*A - B             'according to the table
    return 1 + ret/2                                              '    1  2  3  4  5
end function                                                      '    -------------
                                                                  ' 1| 1  3  6 10 15
function one_to_two( R as ulongint ) as duple                     ' 2| 2  5  9 14 20
    dim as uinteger t = int((-1+sqr(8*R-7))/2)                    ' 3| 4  8 13 19 26
    dim as duple ret                                              ' 4| 7 12 18 25 33 
    ret.A = (t*t+3*t+4)/2-R
    t = int((-1+sqr(8*R-7))/2)                                    'and the inverse of this
    ret.B = R-t*(t+1)/2 
    return ret
end function
 
function rank( N() as ulongint) as ulongint
    dim as uinteger ret, num = ubound(N)+1                        
    if num = 0 then return 0                                      'define a value of 0 for the empty list
    if num = 1 then return two_to_one( N(0), 1 )                  
    ret = two_to_one( N(0), N(1) )                                
    for i as uinteger = 2 to num-1                                'progressively encode the list by 
        ret = two_to_one( ret, N(i) )                             'applying 2to1 on the result of the
    next i                                                        'previous calculation with the next list element
    return two_to_one(ret, num)                                   'store the length of the list as
end function                                                      'the final component
 
sub unrank( R as ulongint, N() as ulongint )
    dim as duple temp
    if R = 0 then                                                 'zero yields the empty list
        redim N(-1)
        return
    end if
    dim as ulongint num, Q(0 to 1)
    temp = one_to_two( R )
    num = temp.B                                                  'first get the length of the encoded list
    redim N(0 to num-1) as ulongint
    if num = 1 then                                               '(singleton handled as a special case)
        N(0)=temp.A
        return
    end if
    for i as integer = num-1 to 2 step -1                         'get back the list elements one by one
        temp = one_to_two( temp.A )                               'in the reverse order they were added
        N(i) = temp.B
    next i
    temp = one_to_two( temp.A )                                   'finally get the initial two list elements
    N(0) = temp.A
    N(1) = temp.B
end sub
 
sub show_list( L() as ulongint )
    dim as integer num = ubound(L)
    if num=-1 then
        print "[]"
        return
    end if
    print "[";
    for i as integer = 0 to num-1
        print str(L(i))+", ";
    next i
    print str(L(num))+"]"
end sub
'A few tests
dim as duple temp
redim as uinteger ex0(-1) 'empty list
dim as ulongint R = rank(ex0())
R = rank(ex0())
print R,
redim as ulongint X(0 to 1)
unrank R, X()
show_list(X())
 
dim as uinteger ex1(0 to 0) = {13}   'list with 1 element
R = rank(ex1())
print R,
unrank R, X()
show_list(X())
 
dim as uinteger ex2(0 to 1) = {19, 361}   'list with 2 elements
R = rank(ex2())
print R,
redim as ulongint X(0 to 1)
unrank R, X()
show_list(X())
 
dim as uinteger ex6(0 to 5) = {1,2,1,2,3,1}   'list with 6 elements
R = rank(ex6())
print R,
unrank R, X()
show_list(X())