Solved

Problems with Fischer-Yates shuffle

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

Is Your AD Toolbox Looking More Like a Toybox?

Managing Active Directory can get complicated.  Often, the native tools for managing AD are just not up to the task.  The largest Active Directory installations in the world have relied on one tool to manage their day-to-day administration tasks: Hyena. Start your trial today.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Handle Exceptions during instantiation 28 417
How to convert MFC::CString to UTF8 wchar_t* 10 216
Best book to learn C++ 4 80
Arduino EDI - Programming language 3 95
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
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 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++.

831 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