As I said earlier, it is easy to be a little bit off when trying to write your own shuffle. The distribution has a significant and repeatable skew when using PJYelton's formula above.
Try running this code and look at the distribution for index 0. Notice how b and c are consistently higher than a, x and y. You can change choice to 2 or 3 to use a better shuffle algorithm that makes the frequencies much closer together.
Code:
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
void BadShuffle(char a[], int size)
{
for (int i=0; i<size; i++)
std::swap(a[i], a[std::rand()%size]);
}
void GoodShuffle(char a[], int size)
{
for (int i=size; i>0; --i)
std::swap(a[i-1], a[std::rand()%i]);
}
void BuiltInShuffle(char a[], int size)
{
std::random_shuffle(a, a + size);
}
void OutputFreq(const std::vector<std::map<char, int> >&, int);
int main()
{
std::srand(static_cast<unsigned>(std::time(0)));
// BadShuffle = 1
// GoodShuffle = 2
// BuiltInShuffle = 3
int choice = 1;
const int arraysize = 25;
char a[arraysize];
std::vector<std::map<char, int> > data(arraysize);
for (int j=0; j < 100000; ++j)
{
for (int i=0; i<arraysize; i++)
a[i] = static_cast<char>('a' + i);
if (choice == 1)
BadShuffle(a, arraysize);
else if (choice == 2)
GoodShuffle(a, arraysize);
else if (choice == 3)
BuiltInShuffle(a, arraysize);
for (int i=0; i<arraysize; i++)
data[i][a[i]]++;
}
for (int index = 0; index < arraysize; ++index)
{
std::cout << '\n';
OutputFreq(data, index);
std::cout << '\n';
}
std::cin.get();
}
void OutputFreq(const std::vector<std::map<char, int> >& data, int index)
{
int lineCnt = 0;
std::cout << "Frequency of char for index: " << index << std::endl;
for (std::map<char, int>::const_iterator iter = data[index].begin(),
end = data[index].end(); iter != end; ++iter)
{
std::cout << iter->first << ':' << iter->second << " ";
if (((++lineCnt) % 5) == 0)
std::cout << std::endl;
}
}
Here is an example output for index 0 in one run:
Code:
Frequency of char for index: 0
a:3975 b:5350 c:5106 d:4941 e:4989
f:4850 g:4695 h:4634 i:4427 j:4233
k:4095 l:4143 m:3921 n:3822 o:3796
p:3701 q:3557 r:3495 s:3301 t:3301
u:3201 v:3185 w:3165 x:3082 y:3035