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
, 3 months ago→{{header|jq}}: simplify
(→{{header|jq}}: simplify) |
|||
| (4 intermediate revisions by the same user not shown) | |||
Line 568:
=={{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'''
Line 576 ⟶ 577:
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.
work using gojq without further qualification.
The C implementation of jq, as of version 1.6, supports arbitrarily
The following is slightly more verbose than it need be but for the▼
support the `include` or `module` directives.▼
Since each Fibonacci-encoded integer ends with "11" and
Line 582 ⟶ 599:
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
the
For example: 1 2 3 => 11 011 0011 =>
In the following, we will simply interpret
▲The Go implementation of jq and, as of version 1.6, the C
this as an integer in base 2 to avoid unnecessary complications
arising from implementation-specific limits.
▲the `tonumber` filter retains precision allowing seamless
▲translation between strings and numbers. Thus, apart from
▲machine limitations, the programs shown here should all work
▲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.
▲===Bijective map based on Fibonacci encoding===
<syntaxhighlight lang="jq">
include "fibonacci" {search: "./"};
# Input: an array of integers
Line 606 ⟶ 614:
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:
| .[1:]
| split("11")
| .[:-1]
Line 625 ⟶ 634:
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
Line 644 ⟶ 654:
'''Invocation''':
<pre>
</pre>
{{output}}
Line 650 ⟶ 660:
{
"numbers": [
],
"encoded": 101000101000001010101000111000001010001000100101100010101010000000010011001001001001000101011000101010100000010000011,
"check": true
}
</pre>
===Bijective map based on "n
<syntaxhighlight lang="jq">
### Infrastructure
| |||