Knuth's algorithm S: Difference between revisions
Content added Content deleted
(added php) |
|||
Line 310: | Line 310: | ||
<pre> 30051 29899 30249 30058 30012 29836 29998 29882 30148 29867</pre> |
<pre> 30051 29899 30249 30058 30012 29836 29998 29882 30148 29867</pre> |
||
=={{header|PHP}}== |
|||
{{works with|PHP|5.3+}} |
|||
<lang php><?php |
|||
function s_of_n_creator($n) { |
|||
$sample = array(); |
|||
$i = 0; |
|||
return function($item) use (&$sample, &$i, $n) { |
|||
$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; |
|||
} |
|||
return $sample; |
|||
}; |
|||
} |
|||
$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++) { |
|||
$s_of_n = s_of_n_creator(3); |
|||
foreach ($items as $item) |
|||
$sample = $s_of_n($item); |
|||
foreach ($sample as $s) |
|||
$bin[$s]++; |
|||
} |
|||
echo "\nTest item frequencies for 100000 runs:\n"; |
|||
print_r($bin); |
|||
?></lang> |
|||
;Sample output: |
|||
<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 |
|||
[8] => 29859 |
|||
[9] => 29984 |
|||
[6] => 29937 |
|||
[7] => 30361 |
|||
[4] => 29994 |
|||
[5] => 29849 |
|||
[0] => 29724 |
|||
[1] => 29997 |
|||
[2] => 30137 |
|||
)</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |