boost - How to find a random bit 1 (or 0) in a dynamic_bit set? -
how find random bit 1 (or 0) in dynamic_bit set?
example:
bitset: 101101 index : 012345 find_random_bit_1() return 3 find_random_bit_0() return 4
the simplest thing keep selecting bits until find 1 you're after:
template <typename t, typename alloc, typename rnd = boost::mt19937> size_t select_random_bit(boost::dynamic_bitset<t, alloc> const& bs, rnd& random, bool target = true) { boost::uniform_int<size_t> pick(0,bs.size()-1); if (bs.empty() || (bs.all() && !target) || (bs.none() && target)) throw std::range_error("select_random_bit"); while(true) { auto index = pick(random); if (bs[index] == target) return index; } throw std::logic_error("select_random_bit"); } the important thing precondition checks avoid infinite loops. of course, performance bad non-uniform data, it's simplest way arrive @ fair distribution
#include <boost/dynamic_bitset.hpp> #include <boost/random.hpp> #include <iostream> #include <stdexcept> template <typename t, typename alloc, typename rnd = boost::mt19937> size_t select_random_bit(boost::dynamic_bitset<t, alloc> const& bs, rnd& random, bool target = true) { boost::uniform_int<size_t> pick(0,bs.size()-1); if (bs.empty() || (bs.all() && !target) || (bs.none() && target)) throw std::range_error("select_random_bit"); while(true) { auto index = pick(random); if (bs[index] == target) return index; } throw std::logic_error("select_random_bit"); } boost::dynamic_bitset<> generate_testdata(boost::mt19937& rng) { boost::dynamic_bitset<> bs(1024+rng()%1024); // [1024,2048) bits boost::uniform_smallint<uint8_t> gen(0, 1); for(size_t = 0; < bs.size(); ++i) bs[i] = gen(rng); return bs; } int main() { using namespace boost; mt19937 rng(42); // seed auto data = generate_testdata(rng); std::cout << data.count() << " out of " << data.size() << " bits set\n"; std::cout << "\ntrue: "; (int = 0; <10; ++i) std::cout << select_random_bit(data, rng/*, true*/) << " "; std::cout << "\nfalse: "; (int = 0; <10; ++i) std::cout << select_random_bit(data, rng, false) << " "; } prints 10 true , 10 false bits, e.g.:
562 out of 1126 bits set true: 1104 394 684 716 624 492 102 817 392 616 false: 335 589 971 785 1069 948 865 290 51 652
Comments
Post a Comment