Re: Re: #18401 [Opn->Ana]: shuffle() broken (fwd)

Tim Converse wrote:

--- Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

Dan Kalowsky wrote:

Anyone able to confirm or deny the validity of this

patch?

---------- Forwarded message ---------- [2002-07-18 01:03:51] adam@trachtenberg.com 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();

I've send the message to Dan, already. Just posting php-dev again. Top elements have more chance than end elements. All elements should have equal chance to be shuffled.

Actually, I think the algorithm of the patched version is correct. It's counterintuitive, but it doesn't matter how many times any slot has an element shuffled out of it.

It may not be intuitive that the algorithm is not perfectly correct. It may be enough for most purposes, though.

What matters is the invariant that whenever elems[n_left] is set, it's being set to an element randomly chosen from the subset of elements that are left (including elems[n_left]), and also that elems[n_left] is not messed with thereafter.

For example, if the last element isn't shuffled, it's stays in as the last element since the last element has only 1 chance to be shuffled. Current code has tendency that last elements stay as last. i.e. Probability of the last element is shuffled is (total_num-1)/total_num. while n th element to be shuffled is obviously has much more chance than last elements. It may be acceptable for most purposes.

You would think that the right thing to do is to set elems[n_left] to a random choice from _all_ the elements in the array, but this leads to some orderings being favored over others. (Check out Intro. to Algo., Cormen, 2nd ed., p 103)

elemes[n_left] to a random choice does not make sense, of course. To give equal chances to be shuffled for all elements, we can write something like for (current=0; current < num_of_elems; current++) { random_index = rand(); RAND_RANGE(random_index, 0, num_of_elems-1, PHP_RAND_MAX); if (array[current] != array[random_index])

    swap(array[current], array[random_index]);

} Current code is almost ok, but this way is correct. This does not require any additional overhead at all, also. -- Yasuo Ohgaki