Solved

Problems with Fischer-Yates shuffle

Posted on 2000-04-26
2
182 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

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
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.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

757 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now