Rosetta Code

Knuth's algorithm S: Difference between revisions

Page Discussion

Knuth's algorithm S (view source)

Revision as of 19:49, 16 March 2024

2,933 bytes added ,  2 months ago
added RPL
m (syntax highlighting fixup automation)
(added RPL)
 
(6 intermediate revisions by 5 users not shown)
Line 624:
 
=={{header|Elena}}==
ELENA 56.0x :
<syntaxhighlight lang="elena">import system'dynamic;
import extensions;
Line 641:
eval(i)
{
counter.append:(1);
 
if (__targetweak self.Length < n)
{
__targetweak self.append:(i)
}
else
{
if(randomGenerator.nextInt:(counter) < n)
{ __targetweak self[randomGenerator.nextInt:(n)] := i }
};
 
^ __targetweak self.Value
}
})
Line 661:
public program()
{
var bin := Array.allocate(10).populate::(n => new Integer());
for(int trial := 0,; trial < 10000,; trial += 1)
{
var s_of_n := 3.s_of_n();
for(int n := 0,; n < 10,; n += 1)
{
var sample := s_of_n.eval:(n);
if (n == 9)
{ sample.forEach::(i){ bin[i].append:(1) } }
}
};
console.printLine:(bin).readChar()
}</syntaxhighlight>
{{out}}
<pre>
3001,3052,3033,2973,2981,3060,3003,2975,2959,2963
3050,3029,3041,2931,3040,2952,2901,2984,3069,3003
</pre>
 
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}}==
Line 1,647 ⟶ 1,718:
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub s_of_n_creator($n) {
my (@sample, $i);
my $i = 0;
-> $item {
if ++$i <= $n { @sample.push: $item }
elsif $i.rand < push$n { @sample,[$n.rand] = $item; }
}@sample
elsif $i.rand < $n {
@sample[$n.rand] = $item;
}
@sample;
}
}
 
my @items = 0..9;
my @bin;
 
for ^100000 {
my &s_of_n = s_of_n_creator( 3);
mysink @sample.&s_of_n for ^9;
for @itemsbin[$_]++ ->for $items_of_n {9;
@sample = s_of_n($item);
}
for @sample -> $s {
@bin[$s]++;
}
}
 
say @bin;</syntaxhighlight>
Output:
Line 1,728 ⟶ 1,788:
frequency of the 8 digit is: 29,976
frequency of the 9 digit is: 29,871
</pre>
 
=={{header|RPL}}==
This is an idiomatic adaptation of the algorithm: SCREA initializes 2 persistent variables: S contains the sample and SPAR the algorithm parameters (n and i)
{{works with|RPL|HP49-C}}
« 0 2 →LIST '<span style="color:green">SPAR</span>' STO { } '<span style="color:green">S</span>' STO
» '<span style="color:blue">SCREA</span>' STO
« <span style="color:green">SPAR</span> EVAL
'''CASE'''
DUP2 > '''THEN''' DROP2 '<span style="color:green">S</span>' STO+ '''END'''
/ →NUM RAND ≥ '''THEN''' <span style="color:green">S</span> DUP SIZE RAND * CEIL ROT PUT '<span style="color:green">S</span>' STO '''END'''
DROP '''END'''
'<span style="color:green">SPAR</span>' 2 DUP2 GET 1 + PUT <span style="color:green">S</span>
» '<span style="color:blue">SOFN</span>' STO
« { } → sample
« { 10 } 0 CON
1 1000 '''START'''
3 <span style="color:blue">SCREA</span>
0
0 9 '''FOR''' k
DROP k <span style="color:blue">SOFN</span>
'''NEXT'''
'sample' STO
« sample k POS » 'k' 0 9 1 SEQ
NOT NOT AXL +
'''NEXT'''
» » '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: [ 206. 218. 235. 309. 359. 329. 327. 324. 359. 334. ]
</pre>
 
Line 1,971 ⟶ 2,063:
</pre>
 
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">import rand
import rand.seed
fn s_of_ncreator(n int) fn(u8) []u8 {
Line 2,012 ⟶ 2,104:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="ecmascriptwren">import "random" for Random
 
var r = Random.new()
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327785...362074"