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
(→{{header|jq}}: simplify) |
|||
Line 568:
=={{header|jq}}==
'''Works with gojq'''
'''Works with jq''' within the limits of jq's support for large integer arithmetic
Line 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.
The
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
The following is slightly more verbose than it need be but for the
sake of compatibility with jaq. Also note that trivial changes would
support the `include` or `module` directives.▼
===Map based on Fibonacci encoding===▼
Since each Fibonacci-encoded integer ends with "11" and
Line 583 ⟶ 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 => 110110011 => 110011011 => 10011011▼
▲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.
In the following, we will simply interpret
▲The following is slightly more verbose than it need be but for the sake of compatibility with jaq. Also note that trivial
this as an integer in base 2 to avoid unnecessary complications
▲changes would be required if using jaq as jaq does not (as of this writing in 2024) support
arising from implementation-specific limits.
▲the `include` or `module` directives.
▲===Map based on Fibonacci encoding===
<syntaxhighlight lang="jq">
include "fibonacci" {search: "./"};
# Input: an array of integers
Line 605 ⟶ 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 624 ⟶ 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 643 ⟶ 654:
'''Invocation''':
<pre>
</pre>
{{output}}
Line 649 ⟶ 660:
{
"numbers": [
],
"encoded": 101000101000001010101000111000001010001000100101100010101010000000010011001001001001000101011000101010100000010000011,
"check": true
}
</pre>
===Bijective map based on "n 0s" encoding===
| |||