How to shuffle an array including the last element?

Question

I've tried using std::random_shuffle and std::shuffle, but they only shuffle the first and elements in between first and last, but not last. Is there a way to shuffle an array (vector) including the last element?

//NumberGenerator.h
#ifndef __NUMBERGENERATOR_H__
#define __NUMBERGENERATOR_H__
#pragma once
#include "Number.h" //regular numbers
#include "MegaNumber.h" //mega numbers
#include <vector> //<vector>
#include <string> //strings 
using std::to_string; //convert int to strings
#include <algorithm> //shuffle
//#include <random> //std::default_random_engine
#define NON_MEGA_COMBINATIONS 5
#define MEGA_COMBINATIONS 1

using std::vector; //<vectors>
using std::string; //string
using std::random_shuffle; //shuffles arrays

class NumberGenerator
{
public:
    NumberGenerator(vector<Number> numbers, vector<MegaNumber> megaNumbers); //constructor
    ~NumberGenerator();
    string pickNumbers(); //function that randomizes regularDraws and megaDraws
protected: 
    vector<Number> regularDraws; //contains number information
    vector<MegaNumber> megaDraws; //contains mega number information
};

#endif


//NumberGenerator.cpp
#include "NumberGenerator.h"


//constructor
NumberGenerator::NumberGenerator(vector<Number> numbers, vector<MegaNumber> megaNumbers)
{
    regularDraws = numbers;
    megaDraws = megaNumbers;
}

//destructor
NumberGenerator::~NumberGenerator()
{
}


string NumberGenerator::pickNumbers()
{
    srand(rand());
    random_shuffle(&regularDraws[1], &regularDraws[regularDraws.size() - 1]);
    random_shuffle(&megaDraws[1], &megaDraws[megaDraws.size() - 1]);
    string regular;
    string mega;
    string last = to_string(regularDraws[regularDraws.size() - 1].getID());

    for (int i = 1; i <= NON_MEGA_COMBINATIONS; i++)
    {
        regular = regular + " " + to_string(regularDraws[i].getID());
    }

    for (int i = 1; i <= MEGA_COMBINATIONS; i++)
    {
        mega = mega + " " + to_string(megaDraws[i].getID());
    }

    return regular + " " + mega + " " + last;
}



//Number.h
#ifndef __NUMBER_H_
#define __NUMBER_H__
#pragma once


class Number
{
public:
    Number(int id); //constructor
    ~Number(); //destructor


    int getID(); //returns the number ID



protected:
    int ID; //This is the number 
};

#endif 

//Number.cpp
#include "Number.h"


//constructor
Number::Number(int id)
{
    occurence = 0;
    occurencePct = 0;
    ID = id;
}

//destructor
Number::~Number()
{
}

//returns the number ID
int Number::getID() 
{
    return ID; 
}


//MegaNumber.h
#ifndef __MEGANUMBER_H__
#define __MEGANUMBER_H__
#pragma once
#include "Number.h"

//Subclass of Number
class MegaNumber :
    public Number
{
public:
    MegaNumber(int id); //Will be inheriting Number superclass
    ~MegaNumber();
};

#endif

//MegaNumber.cpp
#include "MegaNumber.h"


//constructor
MegaNumber::MegaNumber(int id) : Number::Number(id) //inherits the super class Number
{

}

//destructor
MegaNumber::~MegaNumber()
{
}

//Source.cpp
#include <iostream>
#include "NumberGenerator.h"
int main()
{
vector<Number> arg1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<MegaNumber> arg2 = {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9};
NumberGenerator game(arg1, arg2);
  for (int i = 0; i < 10; i++)
  {
      cout << game.pickNumbers() << endl;
  }
}

This is a slimmed down version of my code because it contains 10 files, I think it's enough to make sense though for what I'm doing. Anyhow, The last element doesn't get shuffled each time pickNumbers() is ran.

Answer 1

All standard library algorithms (and other functions) which take a pair of iterators operate on the half-open range [first, last). However, that is no problem at all—all standard library containers are designed so that the iterator returned by end() (and variants) is a past-the-end iterator: it points to one past the last real element in the container. So this call:

std::vector<int> v = whatever();
std::random_shuffle(v.begin(), v.end());

will actually shuffle all the ints in the vector.

In light of this, you can see you're using the function incorrectly. For the last argument, you're passing &regularDraws[regularDraws.size() - 1] (and similar)—the address of the last actual element in the vector. Since the interval is half-open, as I've outlined above, that last element is not part of the shuffle.

You shouldn't be using pointers into the vector at all⁽¹⁾, but iterators instead:

random_shuffle(std::next(regularDraws.begin()), regularDraws.end());

The std::next is there because you were originally passing [1] (the second element in the vector) as the first argument, so I kept that (remember that array indexing is 0-based in C++). If that was not your intention, simply shuffle the entire vector:

random_shuffle(regularDraws.begin(), regularDraws.end());

---

Using half-open ranges everywhere is actually quite advantageous:

• It allows a simple expression of an empty range: begin == end
• All insertion points can be specified using an iterator, if we take that iterator to mean "before the element pointed to." begin then means "insert before the first element," and end translates to "insert before the one-past-last` element," i.e. "insert after the last element."

• It allows easy concatenation/splitting:

  auto b = rng.begin();
  auto e = rng.end();
  auto m = std::next(b, std::distance(b, e) / 2);
  processHalf(b, m);
  processHalf(m, e);
  

---

⁽¹⁾ Your code only works because std::vector stores its elements contiguously in memory. With iterators, it will work with any container.