Hello, I am making a "High Scores" Program from Chapter 4 of Michael Dawson's Introduction To C++ Through Game Programming Book (3rd Edition). In it, a vector consisting of 3 numbers is made and multiple manipulations are made to it through Standard Library Algorithms. There is a situation where the vector's contents have to be randomized and placed in random order, but after the manipulation, their position dosn't seem to change. The code is below:

`

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

using namespace std;


int main()
{
    vector<int>::const_iterator iter;

    cout << "Creating a list of scores.";
    vector<int> scores;
    scores.push_back(1500);
    scores.push_back(3500);
    scores.push_back(7500);

    cout << "\nHigh Scores:\n";
    for (iter = scores.begin(); iter != scores.end(); ++iter)
        cout << *iter << endl;

    cout << "\nFinding a score.";
    int score;
    cout << "\nEnter a score to find: ";
    cin >> score;
    iter = find(scores.begin(), scores.end(), score);
    if (iter != scores.end())
        cout << "Score found.\n";
    else
        cout << "Score not found.\n";

    cout << "\nRandomizing scores.";
    srand(static_cast<unsigned int>(time(0)));
    random_shuffle(scores.begin(), scores.end());
    cout << "\nHigh Scores:\n";


    for (iter=scores.begin();iter!=scores.end();++iter)
    {
        cout << *iter<< endl;
    }

    cout << "\nSorting scores.";
    sort(scores.begin(), scores.end());
    cout << "\nHigh Scores:\n";
    for (iter = scores.begin(); iter != scores.end(); ++iter)
        cout << *iter << endl;

    return 0;
}

`

My Result From The Output Window Is Below:

`
Creating a list of scores.
High Scores:
1500
3500
7500

Finding a score.
Enter a score to find: 355
Score not found.

Randomizing scores.
High Scores:
1500
3500
7500
`

As you can see, after the program "randomly changes the position of the vector's contents," the numbers still remain in order. I have tried seeding my generator with different methods (including the method that is in Michael Dawson's online downloadable code, which BTW, is different than the one that he used in his book). However, I kept getting the same result. Can anybody offer a new perspective on what is going on?

Recommended Answers

All 3 Replies

It looks OK to me! I've just tried compiling and running the code you posted in gcc on Linux, just to make sure I haven't missed anything. And it compiles and runs with no nasty surprises. It all seems to be doing what it should!

The scores are created, the search for a score works OK, the randomise also works and finally the vector gets sorted back into the correct order too.

One thing that you do need to bear in mind is that the example only has three scores in it, so it is highly possible that from time to time, the randomise function will randomly sort the vector into the order it was already in. You could try pushing a few more scores into the vector, that should make the results a bit more varied when the vector is randomised! Basically the more items are in the vector, the less likely it is (statistically speaking) that the randomisation will result in the the vector coming out unchanged!

Also if you want some ideas on randomisation, take a look at Narue's article on the subject.

Thank You!! It Works. I added a coupleof numbers to my vector, and the random library randomised it totally! Also: what would be the recommended minimum size of a vector in order for it to randomized correctly?

I wouldn't say that there is a recommended size per se. You pass your container to the random_shuffle function and it will be randomly shuffled.

And regardless of how many items are in a vector; there is always a chance, however small, that the vector will come out in exactly the same order it was originally in. Statistically speaking, the more items are in the vector that you randomly shuffle, the less likely it is that the vector will come out it's original sequence. And the chances of this happening won't be a linear scale either!

I'm rusty with my statistics, but I guess in mathematical terms you could say that for an array with n items, the chances of the sort coming out in the same order is roughly 1 in n! (where n! is the factorial of n)

So if you only had two items in the vector, you have a 1 in 2 (50%) chance of the array coming out in the same order it went in as (2! = 2*1 = 2).

With three items the odds are about 1 in 6 (3! = 3*2*1 = 6).
With four items, it's about 1 in 24 (4! = 4*3*2*1 = 24).
With five, it's about 1 in 120 (5! = 120)
And so on... I'm sure you get the idea!

And again, regardless of how many items are in the vector; even if the vector does come out in exactly the same order it went in as, it doesn't mean that the random_shuffle algorithm has failed. It just means that the algorithm randomly ordered it in exactly the same sequence. In other words, you just got lucky... Or unlucky, depending on how you look at it! ;)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.