DropZone
asked on
Shuffling algorythm - Explain...
Hello:
I was looking for shuffling algorythms and found some in the PAQ. I also found something called the Fisher-Yates Shuffle in some perl docs. Problem is that, more than implementations, I would like explanations on how they work. You see, I know they work, I can see them work, but I seem to be pretty dense in these matters and get lost when someone starts talking about permutations and n!..... could someone please explain in details the inner workings and theory behind a simple shuffle like:
/* Taken from from Ozo's answer, PAQ Q.10060202 */
for( i=1; i<sizeof(array)/sizeof(arr ay[0]); i+= 1 ){
int r = random()%(i+1);
int temp = array[i]; array[i] = array[r]; array[r] = temp;
}
TIA,
-dZ.
I was looking for shuffling algorythms and found some in the PAQ. I also found something called the Fisher-Yates Shuffle in some perl docs. Problem is that, more than implementations, I would like explanations on how they work. You see, I know they work, I can see them work, but I seem to be pretty dense in these matters and get lost when someone starts talking about permutations and n!..... could someone please explain in details the inner workings and theory behind a simple shuffle like:
/* Taken from from Ozo's answer, PAQ Q.10060202 */
for( i=1; i<sizeof(array)/sizeof(arr
int r = random()%(i+1);
int temp = array[i]; array[i] = array[r]; array[r] = temp;
}
TIA,
-dZ.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
WOW! Thanx...... I completely understand the logic behind it now! :)
Now I see why Ozo and the others talk about factorials and permutations... I get it.... thank you so much. :)
-dZ.
Now I see why Ozo and the others talk about factorials and permutations... I get it.... thank you so much. :)
-dZ.
ASKER
oh... and I always like to give credit where credit is due so... thanx to ozo for the algorythm, the comments in the other answers, and for just being such a cool guy and helping us all when we need it :)
-dZ.
-dZ.
Another way to think of is that at each step, you start with an array with elements 0..i-1 fully shuffled, and produce from that an array with elements 0..i fully shuffled.
ASKER
'i' being the array elements being shuffled in each particular step, not the full array lenght when you start, right?
-dZ.
-dZ.
ASKER
Btw.... ozo and imladris,
someone just pointed out to me something and since I don't really know all that about mathematical probabilities and stuff, i don't know what to make of it:
Wouldn't the first element of the array have more chances of being "shuffled" than the last element? I mean, since everytime that you iterate thru the loop you pick a number from 0 to i, if you have an array of lenght n, the nth element will only be shuffled once (swapped on the last iteration) while the first element (0) has the probability of being swapped around once per every element on the list, since it is within the range of the random number being picked at every iteration. You know what I'm saying? does this make sense?
I understand that if your rand() function picks element (lets say) 0 every time then its not random at all, but if we consider a "perfectly random" number generator, and all numbers have absolutely the same chance to be picked, then that 0th element has good chance of being picked every time, right?
Or am I just getting even more confused?
TIA,
-dZ.
someone just pointed out to me something and since I don't really know all that about mathematical probabilities and stuff, i don't know what to make of it:
Wouldn't the first element of the array have more chances of being "shuffled" than the last element? I mean, since everytime that you iterate thru the loop you pick a number from 0 to i, if you have an array of lenght n, the nth element will only be shuffled once (swapped on the last iteration) while the first element (0) has the probability of being swapped around once per every element on the list, since it is within the range of the random number being picked at every iteration. You know what I'm saying? does this make sense?
I understand that if your rand() function picks element (lets say) 0 every time then its not random at all, but if we consider a "perfectly random" number generator, and all numbers have absolutely the same chance to be picked, then that 0th element has good chance of being picked every time, right?
Or am I just getting even more confused?
TIA,
-dZ.
ASKER
Btw.... ozo and imladris,
someone just pointed out to me something and since I don't really know all that about mathematical probabilities and stuff, i don't know what to make of it:
Wouldn't the first element of the array have more chances of being "shuffled" than the last element? I mean, since everytime that you iterate thru the loop you pick a number from 0 to i, if you have an array of lenght n, the nth element will only be shuffled once (swapped on the last iteration) while the first element (0) has the probability of being swapped around once per every element on the list, since it is within the range of the random number being picked at every iteration. You know what I'm saying? does this make sense?
I understand that if your rand() function picks element (lets say) 0 every time then its not random at all, but if we consider a "perfectly random" number generator, and all numbers have absolutely the same chance to be picked, then that 0th element has good chance of being picked every time, right?
Or am I just getting even more confused?
TIA,
-dZ.
someone just pointed out to me something and since I don't really know all that about mathematical probabilities and stuff, i don't know what to make of it:
Wouldn't the first element of the array have more chances of being "shuffled" than the last element? I mean, since everytime that you iterate thru the loop you pick a number from 0 to i, if you have an array of lenght n, the nth element will only be shuffled once (swapped on the last iteration) while the first element (0) has the probability of being swapped around once per every element on the list, since it is within the range of the random number being picked at every iteration. You know what I'm saying? does this make sense?
I understand that if your rand() function picks element (lets say) 0 every time then its not random at all, but if we consider a "perfectly random" number generator, and all numbers have absolutely the same chance to be picked, then that 0th element has good chance of being picked every time, right?
Or am I just getting even more confused?
TIA,
-dZ.
0, 1, 2, 3, 4
The loop will run from 1 to 5. For each iteration it gets a random number less than or equal to the iteration number. Here goes:
Iteration 1, random number (can be 0 or 1, let suppose it was 0)
This means swap 1 and 0, now we have:
1, 0, 2, 3, 4
Iteration 2, random number (0-2, say 1)
This means swap 2 and 1, now we have:
1, 2, 0, 3, 4
Iteration 3, random number (0-3, say 0)
This means swap 3 and 0, now we have:
3, 2, 0, 1, 4
Iteration 4, random number (0-4, say 2)
This means swap 4 and 2, now we have:
3, 2, 4, 1, 0