Solved

Shuffling algorythm - Explain...

Posted on 2000-02-16
8
402 Views
Last Modified: 2011-10-03
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(array[0]); i+= 1 ){
  int r = random()%(i+1);
  int temp = array[i]; array[i] = array[r]; array[r] = temp;
}


  TIA,
  -dZ.
0
Comment
Question by:DropZone
  • 5
  • 2
8 Comments
 
LVL 16

Accepted Solution

by:
imladris earned 100 total points
ID: 2528702
I'm not in a position to comment on the quality of the algorithm, other than that my experience is that ozo is very good at this stuff. What the loop does is:

The assumption is that the elements of array contain "representations" of the cards in the deck (or whatever you are shuffling.

for( i=1; i<sizeof(array)/sizeof(array[0]); i+= 1 ){
// sizeof(array) will result in the total number of bytes in the array
// sizeof(array[0]) will result in the number of bytes in the first element
// thus sizeof(array)/sizeof(array[0]) is equal to the number of elements in the array
// i.e. it is a general way of setting the number of iterations
 
  int r = random()%(i+1);
//random() (or the more standard rand() return
// a pseudo-random number in the range 0 - RAND_MAX
// by modding it with i+1 you will get a number from 0 to i

  int temp = array[i]; array[i] = array[r]; array[r] = temp;
// shuffle: take the "next" "card" (in array[i])
// and swap it with the card in array[r]

}

 

0
 
LVL 16

Expert Comment

by:imladris
ID: 2528715
So pictorially what is happening is as follows. Suppose array has 5 elements, and they are as follows:

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
0
 
LVL 18

Author Comment

by:DropZone
ID: 2528768
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.
0
Has Powershell sent you back into the Stone Age?

If managing Active Directory using Windows Powershell® is making you feel like you stepped back in time, you are not alone.  For nearly 20 years, AD admins around the world have used one tool for day-to-day AD management: Hyena. Discover why.

 
LVL 18

Author Comment

by:DropZone
ID: 2528776
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.
0
 
LVL 84

Expert Comment

by:ozo
ID: 2529670
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.
0
 
LVL 18

Author Comment

by:DropZone
ID: 2531081
'i' being the array elements being shuffled in each particular step, not the full array lenght when you start, right?

  -dZ.
0
 
LVL 18

Author Comment

by:DropZone
ID: 2531397
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.
0
 
LVL 18

Author Comment

by:DropZone
ID: 2531429
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.
0

Featured Post

Portable, direct connect server access

The ATEN CV211 connects a laptop directly to any server allowing you instant access to perform data maintenance and local operations, for quick troubleshooting, updating, service and repair.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
My eclipse editor won't start ? 4 162
Inorder binary search tree 5 173
An API detour question 7 94
Using popen() and gunzip() to open file in HTTPServer 6 67
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

820 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question