#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <random>
/*
Goal:
- Select N random elements from an vector
- Each selected element must be unique in the entire vector
(i.e., it appears exactly once in the vector)
- The original vector may contain duplicates, but those values
are not eligible for selection.
Approach:
1. Count how many times each value appears (frequency map).
2. Collect indices of elements whose frequency is exactly 1.
3. Randomly sample N indices from that list.
4. Use the indices to access and print the original values.
*/
// Build a frequency map: value -> count
std::unordered_map<int, std::size_t> buildFrequencyMap(const std::vector<int>& data) {
std::unordered_map<int, std::size_t> freq;
freq.reserve(data.size());
for (int value : data) {
++freq[value];
}
return freq;
}
// Collect indices of elements that are unique in the whole vector (frequency == 1)
std::vector<std::size_t> collectGloballyUniqueIndices(
const std::vector<int>& data,
const std::unordered_map<int, std::size_t>& freq
) {
std::vector<std::size_t> uniqueIndices;
uniqueIndices.reserve(data.size());
for (std::size_t i = 0; i < data.size(); ++i) {
int value = data[i];
// Only keep indices of values that appear exactly once in the vector
if (freq.at(value) == 1) {
uniqueIndices.push_back(i);
}
}
return uniqueIndices;
}
// Randomly select N indices from the list of globally unique indices
std::vector<std::size_t> selectRandomUniqueIndices(
const std::vector<std::size_t>& uniqueIndices,
std::size_t N
) {
// Clamp N to the number of available unique elements
N = std::min(N, uniqueIndices.size());
std::vector<std::size_t> result;
result.reserve(N);
std::random_device rd;
std::mt19937 gen(rd());
/*
std::sample:
- Random sampling without replacement
- Perfect for selecting N distinct indices
*/
std::sample(uniqueIndices.begin(), uniqueIndices.end(),
std::back_inserter(result),
N,
gen);
return result;
}
int main() {
// Example vector with duplicates
std::vector<int> data = {
5, 12, 5, 19, 5, 33, 19, 7, 5, 8, 8, 8, 59, 61, 17, 3, 5, 3, 74, 83, 90, 3, 1
};
// Step 1: Build frequency map
auto freq = buildFrequencyMap(data);
// Step 2: Collect indices of values that are unique in the whole vector
auto globallyUniqueIndices = collectGloballyUniqueIndices(data, freq);
// Step 3: Choose how many unique random elements you want
std::size_t N = 5;
// Step 4: Randomly select N indices from the globally unique set
auto randomIndices = selectRandomUniqueIndices(globallyUniqueIndices, N);
// Step 5: Print all globally unique elements (for clarity)
std::cout << "Elements that are unique in the whole vector:\n";
for (std::size_t idx : globallyUniqueIndices) {
std::cout << data[idx] << " ";
}
std::cout << "\n\nRandom selection (" << N << " elements):\n";
// Step 6: Print the randomly selected unique elements
for (std::size_t idx : randomIndices) {
std::cout << data[idx] << " ";
}
}
/*
run:
Elements that are unique in the whole vector:
12 33 7 59 61 17 74 83 90 1
Random selection (5 elements):
12 33 17 83 1
*/
