note 37397 deleted from function.shuffle by bjori
| From: | bjori@php.net | Date: | Tue, 06 Jun 2006 21:35:22 +0000 |
| Subject: | note 37397 deleted from function.shuffle by bjori | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-113386@lists.php.net to get a copy of this message | ||
Note Submitter: Justin Knoll
----
Here's an implementation of a canonical shuffling algorithm.
Its O(n), not O(n^2). The implementation of Fisher-Yates below uses array splicing inside a for loop
over the array, making it O(n^2).
It creates a uniform distribution of permutations - the definition of a shuffle. I'm not sure
that all of the ad hoc algorithms below do this - they might create shuffles that look random on
casual inspection, but aren't.
Many implementations of Fisher-Yates check to make sure that $i != $j before swapping. I figure that
for large lists, that check incurs more cost than just swapping every time.
<?php
/**
* Shuffles an array using the Fisher-Yates shuffle.
*
* D. E. Knuth: The Art of Computer Programming, Volume 2,
* Third edition. Section 3.4.2, Algorithm P, pp 145. Reading:
* Addison-Wesley, 1997. ISBN: 0-201-89684-2.
*
* R. A. Fisher and F. Yates: Statistical Tables. London, 1938.
* Example 12.
*
* @author Justin Knoll
* @param array The array to be sorted - passed by reference.
* @return The shuffled array.
*/
function fisherYatesShuffle(&$array)
{
for ($i = count($array); --$i; $i > 0)
{
$j = @mt_rand(0, $i+1);
$temp = $array[$i];
$array[$i] = $array[$j];
$array[$j] = $temp;
}
}
?>