Re: not enough real programmers?

[bmeyer@bruce.cs.monash.edu.au]

don@news.daedalus.co.nz (Don Stokes) writes:

>Huh?  Assuming "perfect" means "within the parameters of he system's
>random() function", 

>	void
>	shuffle(int array[52]) {
>		int tmparray[52], done[52];
>		int i,j;
[...]
>		for(i = 0; i < 52; i++) {
>			for(j = random() % 52; done[j];) 
>				if(++j == 52) j = 0;
>			array[j] = tmparray[i];
>			done[j] = 1;
>		}
>	}

>works for me.

That doesn't work as well as you think, though. If the card in position
0 is, say, number 17 in the original, then for the card in position 1, you
get the probabilities

   1/52 for 0..16 and 19..51, BUT
   1/26 for 18

That is because both choosing 17 or 18 from the random number generator
will result in 18 being chosen.


Here is one that I _think_ does the right thing (and works in-place),
assuming a "perfect" random number generator:

void shuffle(int* array, int size) {
  int not_done=size;
  int done=0;

  while (not_done>0) {
    int index=random()%not_done;
    int tmp;

    tmp=array[done];
    array[done]=array[done+index];
    array[done+index]=tmp;

    done++;
    not_done--;
  }
}

Bernie


-- 
An activist is the guy who cleans the river, not the guy who
    concludes it's dirty
H. Ross Perot
Independent Presidential candidate in the 1992 US election