BTW, I wrote a simple test program to show the uneven distribution compared to random_shuffle which works pretty well:
Code:
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
void shuffle(int data[], int size)
{
int tempNum;
for(int j = 0; j < size; j++) // loop through the array once
{
int k = std::rand() % size; //Produces a random integer number between 0 and size
tempNum = data[k]; // Pick an int at random
data[k] = data[j]; // swaps the random int and the current int in the loop
data[j] = tempNum;
}
return;
}//! End of shufle Definition
void run_test(bool use_random_shuffle)
{
const int size = 5;
const int iterations = 100000;
int tallies[size][size] = { };
if (use_random_shuffle)
std::cout << "Using random_shuffle:\n";
else
std::cout << "Using shuffle:\n";
for (int i = 0; i < iterations; ++i)
{
int data[size];
for (int j = 0; j < size; ++j)
data[j] = j;
if (use_random_shuffle)
std::random_shuffle(data, data + size);
else
shuffle(data, size);
for (int j = 0; j < size; ++j)
++tallies[j][data[j]];
}
for (int i = 0; i < size; ++i)
{
std::cout << i << ": ";
for (int j = 0; j < size; ++j)
{
std::cout << tallies[i][j] << ' ';
}
std::cout << '\n';
}
std::cout << '\n';
}
int main()
{
std::srand( static_cast<unsigned>(std::time(0)) );
run_test(true);
run_test(false);
run_test(false);
run_test(true);
}
One example of my output:
Code:
Using random_shuffle:
0: 19941 19970 20079 19976 20034
1: 19985 19953 20130 19981 19951
2: 19828 20213 19943 20145 19871
3: 20207 20018 19859 19977 19939
4: 20039 19846 19989 19921 20205
Using shuffle:
0: 19991 24204 20765 18440 16600
1: 20029 18017 23039 20659 18256
2: 19983 18552 17648 22809 21008
3: 20020 19190 18504 17836 24450
4: 19977 20037 20044 20256 19686
Using shuffle:
0: 19723 24367 21115 18393 16402
1: 19965 17808 23249 20619 18359
2: 20258 18419 17323 22965 21035
3: 19944 19290 18527 17978 24261
4: 20110 20116 19786 20045 19943
Using random_shuffle:
0: 19943 20161 19959 19982 19955
1: 19924 20078 20048 19866 20084
2: 20176 19971 19980 19875 19998
3: 19836 19823 20148 20081 20112
4: 20121 19967 19865 20196 19851
Notice that 4 (the last column) only comes in the 0 slot about 16.5% of the time, but it comes up in the 3 slot over 24% of the time with System_159's version (which is a very common mistake when trying to implement this algorithm). With random_shuffle they all will average about 20%.