Solved

Problems with Fischer-Yates shuffle

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

[Webinar] Code, Load, and Grow

Managing multiple websites, servers, applications, and security on a daily basis? Join us for a webinar on May 25th to learn how to simplify administration and management of virtual hosts for IT admins, create a secure environment, and deploy code more effectively and frequently.

Question has a verified solution.

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

Suggested Solutions

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…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

738 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