Index finite lists of positive integers: Difference between revisions
Index finite lists of positive integers (view source)
Revision as of 08:39, 1 February 2024
, 4 months ago→{{header|jq}}: simplify
m (→{{header|Wren}}: Minor tidy) |
(→{{header|jq}}: simplify) |
||
| (16 intermediate revisions by the same user not shown) | |||
Line 566:
37699814998383067155219233
[1, 2, 3, 10, 100, 987654321]</pre>
=={{header|jq}}==
'''Works with gojq'''
'''Works with jq''' within the limits of jq's support for large integer arithmetic
'''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]]). This is the focus of the first
subsection. The second subsection focuses on the "n 0s" encoding.
The Go implementation of jq supports indefinitely large integers and
so, apart from machine limitations, the programs shown here should
work using gojq without further qualification.
The C implementation of jq, as of version 1.6, supports arbitrarily
large literal integers, and the `tonumber` filter retains precision
allowing seamless translation between strings and numbers.
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 (as of this writing in 2024)
support the `include` or `module` directives.
===Map based on Fibonacci encoding===
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 prefix
the binary string with a "1".
For example: 1 2 3 => 11 011 0011 => 1110110011
In the following, we will simply interpret
this as an integer in base 2 to avoid unnecessary complications
arising from implementation-specific limits.
<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(""))
| "1" + join("");
# Input a bitstring or 0-1 integer interpreted as a bitstring
# Output: an array of integers
def unrank:
tostring
| .[1:]
| 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;
### The task
# 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]
| . 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 | jq -nrf index-finite-lists-of-positive-integers.jq
</pre>
{{output}}
<pre>
{
"numbers": [
92408,
42641,
35563,
17028,
49093
],
"encoded": 101000101000001010101000111000001010001000100101100010101010000000010011001001001001000101011000101010100000010000011,
"check": true
}
</pre>
===Bijective map based on "n 0s" encoding===
<syntaxhighlight lang="jq">
### Infrastructure
# Input: a string in base $b (2 to 35 inclusive)
# Output: the decimal value
def frombase($b):
def decimalValue:
if 48 <= . and . <= 57 then . - 48
elif 65 <= . and . <= 90 then . - 55 # (10+.-65)
elif 97 <= . and . <= 122 then . - 87 # (10+.-97)
else "decimalValue" | error
end;
reduce (explode|reverse[]|decimalValue) as $x ({p:1};
.value += (.p * $x)
| .p *= $b)
| .value ;
def binary_digits:
if . == 0 then 0
else [recurse( if . == 0 then empty else ./2 | floor end ) % 2 | tostring]
| reverse
| .[1:] # remove the leading 0
| join("")
end ;
### rank and unrank
# Each integer n in the list is mapped to '1' plus n '0's.
# The empty list is mapped to '0'
def rank:
if length == 0 then 0
else reduce .[] as $i ("";
. += "1" + ("0" * $i))
| frombase(2)
end ;
def unrank:
if . == 0 then []
else binary_digits
| split("1")
| .[1:]
| map(length)
end ;
### Illustration
range(1;11)
| . as $i
| unrank
| . as $unrank
| [$i, $unrank, rank]
</syntaxhighlight>
{{output}}
<pre>
[1,[0],1]
[2,[1],2]
[3,[0,0],3]
[4,[2],4]
[5,[1,0],5]
[6,[0,1],6]
[7,[0,0,0],7]
[8,[3],8]
[9,[2,0],9]
[10,[1,1],10]
</pre>
=={{header|Julia}}==
| |||