Index finite lists of positive integers: Difference between revisions
Index finite lists of positive integers (view source)
Revision as of 04:38, 31 January 2024
, 4 months ago→{{header|jq}}
m (→{{header|Wren}}: Minor tidy) |
|||
Line 566:
37699814998383067155219233
[1, 2, 3, 10, 100, 987654321]</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq'''
'''Works with jaq within the limits of jaq's support for large integers'''
The main point of interest of this entry is probably the use of the
Fibonacci encoding of positive integers (see
e.g. https://en.wikipedia.org/wiki/Fibonacci_coding and
[[:Category:jq/fibonacci.jq]]).
Since each Fibonacci-encoded integer ends with "11" and
contains no other instances of "11" before the end,
the original sequence of integers can trivially be recovered after
simple concatenation of the encodings. However, the Fibonacci
encoding of an integer can begin with 0s, so here we simply reverse
the bit string to produce an ordinary integer.
For example: 1 2 3 => 11 011 0011 => 110110011 => 110011011
The Go implemenation of jq and, as of version 1.6, the C
implementation both support arbitrarily large literal integers, and
the `tonumber` filter retains precision allowing seamless
translation between strings and numbers. Thus, apart from
machine limitations, the programs shown here should all work
for arbitrary positive integers.
The following is slightly more verbose than it need be but for
the sake of compatibility with jaq. Also note that trivial
changes would be required if using jaq as jaq does not support
the `include` or `module` directives.
<syntaxhighlight lang="jq">
include "fibonacci" {search: "./"}; # see https://rosettacode.org/wiki/Category:Jq/fibonacci.jq
# Input: an array of integers
# Output: an integer-valued binary string, being the reverse of the concatenated Fibonacci-encoded values
def rank:
map(fibencode | map(tostring) | join(""))
| join("")
| explode | reverse | implode ;
def unrank:
tostring | explode | reverse | implode
| split("11")
| .[:-1]
| map(. + "11" | fibdecode) ;
# Output: a PRN in range(0;$n) where $n is .
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs) | tostring] | join("") | sub("^0+";"") | tonumber
| if . < $n then . else $n | prn end
end;
# Encode and decode a random number of distinct positive numbers chosen at random.
# Produce a JSON object showing the set of numbers, their encoding, and
# the result of comparing the original set with the reconstructed set.
def task:
(11 | prn) + 1
| . as $numbers
| [range(0;$numbers) | 100000 | prn + 1]
| unique # ensure there are no duplicates
| . as $numbers
| rank
| . as $encoded
# now decode:
| unrank
| {$numbers, encoded: ($encoded|tonumber), check: ($numbers == .)}
;
task
</syntaxhighlight>
'''Invocation''':
<pre>
< /dev/random tr -cd '0-9' | fold -w 1 | jaq -nrf index-finite-lists-of-positive-integers.jq
</pre>
{{output}}
<pre>
{
"numbers": [
1906,
3613,
12749,
17649,
29526,
38186,
38358,
68497,
69273,
90245,
96788
],
"encoded": 1100100010101001000100010110001010000000100000010111010010010000000100100011010010000010000000010111001010000101001010001110010100000100100000101100000001010000100100011010101010010100100111000100001010000101011010000001001000011000100101000000,
"check": true
}
</pre>
=={{header|Julia}}==
| |||