1

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;
}
user3243499
  • 2,953
  • 6
  • 33
  • 75
  • 5
    Side notes: (1) `#include `: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h, (2) `using namespace std;`: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice. – wohlstad Jan 30 '23 at 15:58
  • 4
    what is the actual aim? You could either find all occurences of 1 then pick one at random, or you could randomly shuffle or rotate the vector, to find a 1 at random, though whats the point? What makes one 1 better or worse than the other ? – 463035818_is_not_an_ai Jan 30 '23 at 16:00
  • maybe what you actually want is a random integer `0 < x <= 3`, so you can pick randomly between one of the three indices – 463035818_is_not_an_ai Jan 30 '23 at 16:05
  • 4
    This is a reasonable question. The criteria are clear enough, and it's simplified to just the basics. Of course, once simplified to a toy problem, it's not very useful anymore, but that's not a reason for a downvote. What makes this interesting is the question whether you need to create the set of possible answers `[3, 4, 6]`. (potentially O(n)) – MSalters Jan 30 '23 at 16:06
  • 1
    @463035818_is_not_a_number: Do you count first, and then iterate over the list a second time? That could be a good answer, but there are other options. – MSalters Jan 30 '23 at 16:08

3 Answers3

3

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

Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
3

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) {
            /* Found new minimum. */
            min = first;
            mincnt = 1;
        } else if (*first == *min) {
            /* If equal to the minimum, select this with probability 1/mincnt + 1.
             * Second has 1/2 chance to be selected, third has 1/3, etc. */
            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;
    }
}

Demo of the above

Hasturkun
  • 35,395
  • 6
  • 71
  • 104
0

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

Something Something
  • 3,999
  • 1
  • 6
  • 21