• Status: Solved
• Priority: Medium
• Security: Public
• Views: 206

# Problems with Fischer-Yates shuffle

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
mm162
1 Solution

Commented:
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}.

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

Commented:
// 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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.