?
Solved

Problems with Fischer-Yates shuffle

Posted on 2000-04-26
2
Medium Priority
?
198 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
2 Comments
 
LVL 3

Accepted Solution

by:
mnewton022700 earned 300 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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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 be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses

800 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