--- Yasuo Ohgaki <[EMAIL PROTECTED]> wrote:
> Dan Kalowsky wrote:
> > Anyone able to confirm or deny the validity of this
> patch?
> >
> >
> > ---------- Forwarded message ----------
> >
> > [2002-07-18 01:03:51] [EMAIL PROTECTED]
> >
> > 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.
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.
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)
--tim
__________________________________________________
Do You Yahoo!?
HotJobs - Search Thousands of New Jobs
http://www.hotjobs.com
--
PHP Development Mailing List <http://www.php.net/>
To unsubscribe, visit: http://www.php.net/unsub.php
