I have a vector of integers as follows: vector<int> vec {3, 4, 2, 1, 1, 3, 1}. Below code always returns the minimum element of 1 at index 3. How to make it randomly chose the minimum value of 1 from three locations [3, 4, 6] when same code is run multiple times?

#include <bits/stdc  .h>
using namespace std;

int main() {
    vector<int> vec {3, 4, 2, 1, 1, 3, 1};
    auto it = min_element(vec.begin(), vec.end());
    cout << *it << endl;
    cout << "It is at a distance of: " << distance(vec.begin(), it) << endl;
    return 0;
}

CodePudding user response：

There are probably many ways to do this depending on your needs. Here's one:

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

int main() {
    // a seeded random number generator
    std::mt19937 prng(std::random_device{}());

    std::vector<int> vec {3, 4, 2, 1, 1, 3, 1};

    // get the min iterator to the first minimum element:
    auto mit = std::min_element(vec.begin(), vec.end());

    // collect the indices of all elements equal to the min element:
    std::vector<std::size_t> ids;
    for(auto fit = mit; fit != vec.end(); fit = std::find(fit   1, vec.end(), *mit))
    {
        ids.push_back(std::distance(vec.begin(), fit));
    }

    // a distribution to select one of the indices in `ids`:
    std::uniform_int_distribution<std::size_t> dist(0, ids.size()-1);
    
    // print 10 randomly selected indices
    for(int i = 0; i < 10;   i) {
        std::cout << ids[dist(prng)] << '\n';
    }
}

Demo

CodePudding user response：

Here's a single-pass variation based on selection sampling (though it could probably be made nicer), essentially being a case of Reservoir Sampling with a sample size of 1.

#include <iostream>
#include <random>
#include <vector>
#include <iterator>

template <typename T, typename URBG>
T rmin(T first, T last, URBG &g) {
    if (first == last) return first;
    T min = first;

    using ud = std::uniform_int_distribution<std::size_t>;
    using param_type = ud::param_type;
    ud d;

    std::size_t mincnt = 1;
      first;
    while (first != last) {
        if (*first < *min) {
            min = first;
            mincnt = 1;
        } else if (*first == *min) {
            auto k = d(g, param_type{0, mincnt  });
            if (!k) {
                min = first;
            }
        }
          first;
    }

    return min;
}

int main() {
    // a seeded random number generator
    std::mt19937 prng(std::random_device{}());

    std::vector<int> vec{3, 4, 2, 1, 1, 3, 1};

    for (int i = 0; i < 10; i  ) {
        auto it = rmin(vec.begin(), vec.end(), prng);
        std::cout << *it
                  << " is at a distance of: " << std::distance(vec.begin(), it)
                  << std::endl;
    }
}

CodePudding user response：

This solution is random but likely does not give equal probability to all entries. However it avoids having to create new vectors and it is still O(N).

It works by randomly splitting the sequence (in logical sense) in two parts and taking the minimum of each. Then you return the minimum of the two parts.

As I said, it is likely not uniformly distributed but it is indeed still random.

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

template< typename T >
T minimum( T begin, T end ) {
    std::size_t size = std::distance( begin, end );
    if ( size<=1 ) return begin;

    std::random_device rd;  
    std::mt19937 gen(rd()); 
    std::uniform_int_distribution<size_t> ds(1,size-1);

    auto sep = begin   ds(gen);
    auto it1 = std::min_element(begin, sep );
    auto it2 = std::min_element(sep, end );
    if ( *it1<*it2 ) return it1;
    return it2;
}

int main() {
    std::vector<int> vec {3, 4, 2, 1, 1, 3, 1};
    for ( int j=0; j<10;   j ) {
        auto it = minimum( vec.begin(), vec.end() );
        std::cout << *it << " is at a distance of: " << std::distance(vec.begin(), it) << std::endl;
    }
    return 0;
}

Produces

Program returned: 0
1 is at a distance of: 4
1 is at a distance of: 3
1 is at a distance of: 6
1 is at a distance of: 3
1 is at a distance of: 6
1 is at a distance of: 3
1 is at a distance of: 4
1 is at a distance of: 3
1 is at a distance of: 3
1 is at a distance of: 6

Godbolt: https://godbolt.org/z/3EhzdGndz