Generate Random 20 Non-repeating numbers in C++

Viewed 165

So I have a program where I generate a 8x8 matrix which are rooms. So we have 64 rooms. Now I have to generate 20 random rooms to be dirty. I'm trying to figure out how I can generate 20 non repeating numbers to use as the dirty rooms. This is my code so far:

//generate the 20 random dirty rooms 
int col;
int row;

for (int i = 0; i < 20; i++)
{
    col = ranNumber();
    row = ranNumber();
    cout << "\t" << col << "  " << row << endl;

    if (room[row][col] == 'D')
    {
        cout << "Duplicate" << endl;
        col = ranNumber();
        row = ranNumber();
        cout << "New number " << row << col << endl;
        room[row][col] = 'D';

    }
    else

        //set the room as dirty 
        room[row][col] = 'D';
}

*ranNumber():

int ranNumber() {
   return rand() % 8;
}
4 Answers

Since you're not dealing with a particularly large data set, I'd suggest using std::shuffle. You'll want to initialize your rooms with 20 dirty (the positions don't matter, so do whatever is easiest), then let std::shuffle rearrange the rooms. This avoids you having to write your own loop in case you get poor luck with your random generator, and better expresses your intent.

Sample code:

int main() {
    char rooms[8][8];
    for(auto i = 0; i < 8; ++i) {
        for(auto j = 0; j < 8; ++j) {
            rooms[i][j] = (i == 0) ? 'D' : ' ';
        }
    }
    printRooms(rooms);
    std::random_device rd{};
    std::default_random_engine re{rd()};
    auto b = (char *) rooms;
    std::shuffle(b, b + (8 * 8), re);
    std::cout << "----------------------\n";
    printRooms(rooms);
    return 0;
}

You can create an array of room numbers (0-63) and use as a picking basket. Whenever a room has been picked, you swap that room out of the selectable range.

Example:

#include <algorithm> // fill_n
#include <iostream>
#include <numeric>   // iota
#include <random>    // mt19937, random_device, uniform_int_distribution

int main() {
    std::mt19937 prng(std::random_device{}()); 
    char room[8][8];
    constexpr int room_count = 8 * 8;
    std::fill_n(&room[0][0], room_count, '.'); // fill rooms with an initial value.

    char numbers[room_count];
    std::iota(std::begin(numbers), std::end(numbers), 0); // 0 - 63

    for(int i = 1; i <= 20; ++i) {
        int last_selectable_room = room_count - i;
        std::uniform_int_distribution<int> dist(0, last_selectable_room);
        auto& selected = numbers[dist(prng)];
        *(&room[0][0] + selected) = 'D';
        // swap the selected room number with the last selecable room number
        // to make sure that the selected room can't be selected again
        std::swap(selected, numbers[last_selectable_room]);
    }
}

Demo

This is likely going to be 2.3 - 2.4 times faster than the std::shuffle approach if you use g++ or clang++. Benchmark

If selecting the dirty rooms uniformly at random is truly important, you could build a random permutation of the rooms using Knuth's shuffle (be careful, it is easy to blunder!) and picking e.g. the first 20 ones of the result as dirty.

You could do it using std::shuffle() and a single-dimension array, exploiting the fact that an m x n matrix can be represented as an array containing m*n elements

#include <vector>
#include <random>
#include <algorithm>

class random_room_generator {
public:
    random_room_generator(const size_t matrixRows, const size_t matrixColumns) :
        m_matrixRows(matrixRows),
        m_randomRoomList(),
        m_nextRoom(0)
    {
        // Create a list of all the room numbers.
        const size_t totalRooms = matrixRows * matrixColumns;
        for (size_t i = 0; i < totalRooms; ++i) {
            m_randomRoomList.push_back(i);
        }

        // Shuffle the list.
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(m_randomRoomList.begin(), m_randomRoomList.end(), g);
    }

    std::pair<size_t, size_t> next() {
        // Get the room number:
        const size_t roomNumber = m_randomRoomList[m_nextRoom++];

        if (m_nextRoom == m_randomRoomList.size()) {
            // Loop back round to the start if we get to the end of the shuffled list.
            m_nextRoom = 0;
        }

        // Convert the room number into a row and column using the modulus/division operators:
        return std::pair<size_t, size_t>(roomNumber % m_matrixRows, roomNumber / m_matrixRows);
    }

private:
    size_t m_matrixRows;
    std::vector<size_t> m_randomRoomList;
    size_t m_nextRoom;
};

Then, in your function, instead of calling ranNumber(), you can use an instance of random_room_generator to save a list of random rooms and then get 20 rooms from that list:

random_room_generator gen(8, 8);

for (int i = 0; i < 20; i++)
{
    std::pair<size_t, size_t> roomCoords = gen.next();
    const size_t row = roomCoords.first;
    const size_t col = roomCoords.second;
    
    cout << "\t" << col << "  " << row << endl;

    //set the room as dirty 
    room[row][col] = 'D';
}

You can find a working example here: https://godbolt.org/z/xKLmjm

Related