Implementing a Fisher-Yates Algorithm in C++

[John Aldrich]

I have some old perl code that I found in the book "Perl Database Programming" by Brent Michalski that I need to port to C++ for use with another project that needs in place array shuffling. I've analyzed the perl code back to front and am still not sure how implement the same thing in C++. For inspection, I have the full source for the perl subroutine with line by line comments verbatim from the book for those who don't have an understanding of perl following the source code:

1: sub fisher_yates_shuffle {
2:     my $array = shift;      
3:     my $i;             
4:     for($i = @$array; --$i) {
5:        my $j = int rand ($i+1);
6:        next if $i == $j;
7:        @$array[$i,$j] = @$array[$j,$i];
8:     }
9: } 

Line 1 begins the fisher_yates_shuffle subroutine. This subroutine is designed to take a reference to an array as the input, and it will randomize the items in the array in place. This means that we pass a reference to an array and the array gets randomized. This is a commonly used method for randomizing arrays, the "Fisher-Yates shuffle," named after Sir Ronald A. Fisher and Frank Yates, who introduced the algorithm in example 12 of their 1938 book Statistical Tables. Line 2 declares a scalar variable named $array and shifts the value passed to the subroutine into it. This value should be a reference to an array. Line 3 declares a scalar variable named $i Line 4 begins a for loop that sets $i to the current value each time through the loop and also decrements $i. This has the effect of setting $i to the number of elements in the array @$array and then counting down one by one. Line 5 declares a scalar variable named $j and sets it to a random integer between 1 and $i Line 6 causes the for loop to skip to the next iteration if $i and $j are equal Line 7 swaps the values at $array[$i] and $array[$j] Line 8 ends the for loop that we began on Line 6 Line 9 ends this subroutine. As I've said, I've been over this thing a dozen times, and a solution in C++ just isn't coming to me, so I'd appreciate any help that anyone woudl be will to provide. I think that the perl source I've included gives enough of a general idea of what needs to happen along with the

[AlexO]

template <class T> inline void fisher_yates_shuffle(T* array, int size) { ::srand(static_cast<unsigned int>(::time(0))); //could be for(int i = size - 1;i > -1;--i) { int j = ::rand() % i;//could be "::rand() % i + 1" I am not sure what "rand ($i+1)" stands for if(i != j) { T temp = array[i]; array[i] = array[j]; array[j] = temp; } } }

[Ryan Binns]

Almost... :) The rand() % i should be rand() % (i+1). Other than that, well done ;).

template <class T>
inline void fisher_yates_shuffle(T* array, int size)
{
srand(static_cast<unsigned int>(time(0)));
for(int i=size-1; i>-1; --i)
{
int j = rand() % (i + 1);
if(i != j)
{
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}

Ryan Being little and getting pushed around by big guys all my life I guess I compensate by pushing electrons and holes around. What a bully I am, but I do enjoy making subatomic particles hop at my bidding - Roger Wright (2nd April 2003, The Lounge)
Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late - John Nichol "Point Of Impact"

[Ryan Binns]

Very similar to Alex's reply above, except the rand() % i should be rand() % (i+1):

template <class T>
inline void fisher_yates_shuffle(T* array, int size)
{
srand(static_cast<unsigned int>(time(0)));
for(int i=size-1; i>-1; --i)
{
int j = rand() % (i + 1);
if(i != j)
{
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}

Ryan Being little and getting pushed around by big guys all my life I guess I compensate by pushing electrons and holes around. What a bully I am, but I do enjoy making subatomic particles hop at my bidding - Roger Wright (2nd April 2003, The Lounge)
Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late - John Nichol "Point Of Impact"