Knuth's algorithm S: Difference between revisions
→{{header|jq}}
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
|||
Line 1,029:
<pre>[29965, 30178, 29956, 29957, 30016, 30114, 29977, 29996, 29982, 29859]</pre>
=={{header|jq}}==
'''Adapted from [[#Wren]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''.
jq does not support functions that return functions,
so we adopt the approach taken for example by the [[#C|C]] entry.
Specifically, following the [[#Wren|Wren]] model, the closure variables
are encapsulated in a JSON object of the form {n, s, next, m},
which is initially
<pre>
{n: $n, s: [range(0;$n)|0], next: 0, m: $n}
</pre>
where $n is the maximum sample size.
In the following, /dev/random is used as a source of entropy.
In a bash or bash-like environment, a suitable invocation would
be as follows:
<pre>
< /dev/random tr -cd '0-9' | fold -w 1 | jq -Mcnr algorithm-s.jq
</pre>
'''algorithm-s.jq'''
<syntaxhighlight lang=jq>
# Output: a PRN in range(0; .)
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
# Input and output: {n, s, next, m}
# The initial input should be
# {n: $n, s: [range(0;$n)|0], next: 0, m: $n}
# where $n is the maximum sample size.
def sOfN(items):
if (.next < .n)
then .s[.next] = items
| .next += 1
else .m += 1
| if ((.m | prn) < .n)
then (.n | prn) as $t
| .s[$t] = items
| if .next <= $t
then .next = $t + 1
else .
end
else .
end
end;
def task($iterations):
def dim($n): [range(0;$n)|0];
def init($n): {n: $n, s: dim($n), next: 0, m: $n };
reduce range(0; $iterations) as $r ( {freq: dim(10) };
reduce range(48; 57) as $d (. + init(3); sOfN($d) )
| reduce sOfN(57).s[] as $d (.;
.freq[$d - 48] += 1) )
| .freq ;
task(1e5)
</syntaxhighlight>
{{output}}
<pre>
[30008,29988,29827,30101,30308,30005,29808,29851,30218,29886]
</pre>
=={{header|Julia}}==
| |||