Solved

Problems with Fischer-Yates shuffle

Posted on 2000-04-26
2
188 Views
Last Modified: 2010-04-02
int Array[3] = {0,1,2}

I want an algorithm that will shuffle the order of this array randomly, so that the following six combinations are all equally likely:
{0,1,2}
{0,2,1}
(1,0,2}
{1,2,0}
{2,0,1}
{2,1,0}

Tbe following Fischer-Yates shuffle I was using yields only the combinations {2,0,1} and {1,2,0}:

for (int l=1,l<3,l++)
{ int r = random(l);
  int temp = Array[l];
  Array[l] = Array[r];
  Array [r] = temp;
}

0
Comment
Question by:mm162
2 Comments
 
LVL 3

Accepted Solution

by:
mnewton022700 earned 100 total points
ID: 2753589
I am going to assume that random(i) returns a random greater than or equal to 0 and less than i. If this is not the case the following comment will not be correct.

Your current code will first swap Array[1] with Array[0] to produce {1,0,2} and then swap Array[2] with either Array[0] or Array[1] to produce either {2,0,1} or {1,2,0}.

Try this instead:

for (int i = 2, i > 0 ,i--)
{
  int r = random(i + 1);
  int temp = Array[i];
  Array[i] = Array[r];
  Array[r] = temp;
}

On the first iteration this will produce one of:
{0,1,2} {0,2,1} {2,1,0}

And on the second will produce one of:
{0,1,2} {1,0,2} {0,2,1} {2,0,1} {2,1,0} {1,2,0}

Let me know if my first assumption was wrong and I will fix the algorithm for you.
0
 
LVL 84

Expert Comment

by:ozo
ID: 2754232
// or
for (int l=1,l<3,l++)
{ int r = random(l+1);
  int temp = Array[l];
  Array[l] = Array[r];
  Array [r] = temp;
}
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

828 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