Bug #18401: shuffle() broken
| From: | adam at trachtenberg dot com | Date: | Thu, 18 Jul 2002 05:03:52 +0000 |
| Subject: | Bug #18401: shuffle() broken | ||
| Groups: | php.bugs | ||
| Request: | Send a blank email to php-bugs+get-14493@lists.php.net to get a copy of this message | ||
From: adam@trachtenberg.com
Operating system: Redhat 7.3
PHP version: 4CVS-2002-07-18
PHP Bug Type: Arrays related
Bug description: shuffle() broken
The shuffle() function in the CVS is (still) broken. It does not correctly
generate all possible combinations of the array. (I know this function was
recently updated, this test is with new version.)
Here is a diff to fix the problem:
--- array.c Thu Jul 18 00:50:54 2002
+++ array.new.c Thu Jul 18 00:49:35 2002
@@ -1441,7 +1441,7 @@
{
Bucket **elems, *temp;
HashTable *hash;
- int j, n_elems, cur_elem = 0, rnd_idx, n_left;
+ int j, n_elems, rnd_idx, n_left;
n_elems = zend_hash_num_elements(Z_ARRVAL_P(array));
@@ -1457,13 +1457,12 @@
elems[j++] = temp;
while (--n_left) {
rnd_idx = php_rand(TSRMLS_C);
- RAND_RANGE(rnd_idx, cur_elem, n_left, PHP_RAND_MAX);
- if (rnd_idx != cur_elem) {
- temp = elems[cur_elem];
- elems[cur_elem] = elems[rnd_idx];
+ RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX);
+ if (rnd_idx != n_left) {
+ temp = elems[n_left];
+ elems[n_left] = elems[rnd_idx];
elems[rnd_idx] = temp;
}
- cur_elem++;
}
HANDLE_BLOCK_INTERRUPTIONS();
Here is some PHP that will reproduce the problem. As you can see the
built-in shuffle() only generates 3 of the 6 possible combinations, while
the userland array_shuffle() correctly generates all 6 with equal
likelyhood.
<?php
function array_shuffle(&$array) {
$i = count($array);
while (--$i) {
$j = mt_rand(0, $i);
if ($i != $j) {
/* swap elements */
$tmp = $array[$j];
$array[$j] = $array[$i];
$array[$i] = $tmp;
}
}
}
function test($function) {
$a = array();
for ($i = 0; $i < 10000; $i++) {
$p = range(1,3);
$function($p);
$s = join('', $p);
$a[$s]++;
}
print "$function\n";
foreach($a as $k => $v) {
print "$k: $v\n";
}
}
test('shuffle');
test('array_shuffle');
?>
--
Edit bug report at http://bugs.php.net/?id=18401&edit=1
--
Fixed in CVS: http://bugs.php.net/fix.php?id=18401&r=fixedcvs
Fixed in release: http://bugs.php.net/fix.php?id=18401&r=alreadyfixed
Need backtrace: http://bugs.php.net/fix.php?id=18401&r=needtrace
Try newer version: http://bugs.php.net/fix.php?id=18401&r=oldversion
Not developer issue: http://bugs.php.net/fix.php?id=18401&r=support
Expected behavior: http://bugs.php.net/fix.php?id=18401&r=notwrong
Not enough info: http://bugs.php.net/fix.php?id=18401&r=notenoughinfo
Submitted twice: http://bugs.php.net/fix.php?id=18401&r=submittedtwice
register_globals: http://bugs.php.net/fix.php?id=18401&r=globals