Knuth's algorithm S: Difference between revisions

Content added Content deleted
(added php)
(added perl)
Line 310:
 
<pre> 30051 29899 30249 30058 30012 29836 29998 29882 30148 29867</pre>
 
=={{header|Perl}}==
<lang perl>use strict;
 
sub s_of_n_creator {
my $n = shift;
Item: 0 ->my @sample: 0;▼
my $i = 0;
sub {
my $item = shift;
$i++;
if ($i <= $n) {
# Keep first n items
push @sample, $item;
} elsif (rand() < $n / $i) {
# Keep item
$ @sample[rand $n] = $s_of_n($item);▼
}
@sample
}
}▼
 
my @items = (0..9);
my @bin;
 
foreach (my $itemstrial as(1 $item.. 100000) {▼
my $s_of_n = s_of_n_creator(3);▼
Item: 1 ->my @sample: 0, 1;▼
foreach my $item (@items) {
@sample = $s_of_n->($item);
}
foreach my $s (@sample) {
$bin[$s]++;
}
}
print "@bin\n";
</lang>
 
;Sample output:
<pre>30003 29923 30192 30164 29994 29976 29935 29860 30040 29913</pre>
 
=={{header|PHP}}==
Line 320 ⟶ 360:
$i++;
if ($i <= $n) {
#// Keep first n items
$sample[] = $item;
} else if (rand(0, $i-1) < $n) {
#// Keep item
$sample[rand(0, $n-1)] = $item;
}
Line 331 ⟶ 371:
 
$items = range(0, 9);
echo "Single run samples for n = 3:\n";
▲$s_of_n = s_of_n_creator(3);
▲foreach ($items as $item) {
▲ $sample = $s_of_n($item);
echo " Item: $item -> sample: ", implode(', ', $sample), "\n";
▲}
 
for ($trial = 0; $trial < 100000; $trial++) {
Line 345 ⟶ 379:
$bin[$s]++;
}
echo "\nTest item frequencies for 100000 runs:\n";
print_r($bin);
?></lang>
 
;Sample output:
<pre>Array▼
<pre>Single run samples for n = 3:
▲ Item: 0 -> sample: 0
▲ Item: 1 -> sample: 0, 1
Item: 2 -> sample: 0, 1, 2
Item: 3 -> sample: 0, 3, 2
Item: 4 -> sample: 0, 3, 2
Item: 5 -> sample: 0, 3, 2
Item: 6 -> sample: 0, 3, 2
Item: 7 -> sample: 0, 3, 2
Item: 8 -> sample: 0, 3, 2
Item: 9 -> sample: 0, 3, 2
 
Test item frequencies for 100000 runs:
▲Array
(
[3] => 30158
Retrieved from "https://rosettacode.org/wiki/Knuth%27s_algorithm_S"