Question

How to generate a random integer from a range [0, N] that is not in a unique integer list with C++

Answer 1

#include <iostream>
#include <vector>
#include <unordered_set>
#include <random>

// Function to generate a random integer in [0, N] excluding given numbers
int randomExcluding(int N, const std::vector<int>& exclude) {
    if (N < 0) {
        throw std::invalid_argument("N must be non-negative.");
    }

    // Store excluded numbers in a hash set for O(1) lookup
    std::unordered_set<int> excludedSet(exclude.begin(), exclude.end());

    // Build a list of allowed numbers
    std::vector<int> allowed;
    allowed.reserve(N + 1 - excludedSet.size());
    for (int i = 0; i <= N; i++) {
        if (excludedSet.find(i) == excludedSet.end()) {
            allowed.push_back(i);
        }
    }

    if (allowed.empty()) {
        throw std::runtime_error("No available numbers to choose from.");
    }

    // Random number generator
    std::random_device rd;  // Non-deterministic seed
    std::mt19937 gen(rd()); 
    std::uniform_int_distribution<> dist(0, static_cast<int>(allowed.size()) - 1);

    return allowed[dist(gen)];
}

int main() {
    try {
        int N = 14;
        std::vector<int> exclude = {2, 5, 7}; // Unique integers to exclude

        int randomNum = randomExcluding(N, exclude);
        std::cout << "Random number (excluding list) = " << randomNum << "\n";
    }
    catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << "\n";
    }
}


/*
run:

Random number (excluding list) = 4

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <random>
#include <algorithm> // find

int randomExcluding(int N, const std::vector<int>& excluded) {
    // If all numbers are excluded, return -1 or throw exception
    if (excluded.size() > static_cast<size_t>(N + 1)) {
        return -1;
    }
    
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, N);
    
    int num;
    do {
        num = dis(gen);
    } while (std::find(excluded.begin(), excluded.end(), num) != excluded.end());
    
    return num;
}

int main() {
    std::vector<int> excluded = {2, 5, 7};
    int N = 14;
    
    std::cout << randomExcluding(N, excluded) << " ";
}



/*
run:

12

*/

 

70+ SQL courses for beginners and professionals

Answer 3

#include <iostream>
#include <vector>
#include <unordered_set>
#include <random>

int randomExcludingSet(int N, const std::vector<int>& excluded) {
    std::unordered_set<int> excludedSet(excluded.begin(), excluded.end());
    
    if (excludedSet.size() > static_cast<size_t>(N + 1)) {
        return -1; // All numbers excluded
    }
    
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, N);
    
    int num;
    do {
        num = dis(gen);
    } while (excludedSet.count(num) > 0);
    
    return num;
}

int main() {
    std::vector<int> excluded = {2, 5, 7};
    int N = 14;
    
    std::cout << randomExcludingSet(N, excluded) << " ";
}


/*
run:

11

*/

 

70+ SQL courses for beginners and professionals