Index finite lists of positive integers: Difference between revisions
Index finite lists of positive integers (view source)
Revision as of 16:59, 5 November 2020
, 3 years agoadd FreeBASIC
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: Fix link: Perl 6 --> Raku) |
(add FreeBASIC) |
||
Line 24:
Make the ''rank'' function as a [[wp:bijection| <u>bijection</u>]] and show ''unrank(n)'' for <big>'''n'''</big> varying from '''0''' to '''10'''.
<br><br>
=={{header|FreeBASIC}}==
Restricted to shortish lists with smallish integers, because the rank integers get really big really fast, and bloating the code with arbitrary precision arithmetic isn't illustrative.
<lang FreeBASIC>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 encded 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())</lang>
{{out}}
<pre>0 []
79 [13]
2591460030 [19, 361]
9576882 [1, 2, 1, 2, 3, 1]</pre>
=={{header|D}}==
| |||