Index finite lists of positive integers: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy) |
|||
Line 566: | Line 566: | ||
37699814998383067155219233 |
37699814998383067155219233 |
||
[1, 2, 3, 10, 100, 987654321]</pre> |
[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}}== |
=={{header|Julia}}== |