Выбрать подмножество случайных элементов на карте

Question

У меня есть карта элементов:

   std::map<char,int> values;

   values['a']=10;
   values['b']=30;
   values['c']=50;
   values['d']=70;
   values['e']=90;
   values['f']=100;
   values['g']=120;

Поэтому мне нужно выбрать N элементов из values в качестве карты пар предпочтительно (формат вывода, а также формат ввода).

Я пробовал другие различные решения от stackoverflow, но они в основном применимы для вектора, а не для любого типа контейнера C ++ 11 или выглядят слишком сложными для меня.

Мне нужен более эффективный способ, чем просто random_shuffle, который на самом деле мутирует Контейнер C ++.

Также было бы неплохо, если бы эта функция была применима для любого типа контейнера C ++.

Answer 1

Вы можете скопировать ключи std::map<char, int> в std::vector<char>. Затем перемешайте этот вектор с std::random_shuffle ^X . Наконец, верните num элементов карты: те, чьи ключи являются num последними ключами в векторе:

std::vector<std::pair<char, int>> pick_random(const std::map<char, int>& m, size_t num)
{
   std::vector<char> keys;
   keys.reserve(m.size());

   // copy the map's keys    
   std::transform(m.begin(), m.end(), std::back_inserter(keys),
      [](const std::pair<const char, int>& p) {
         return p.first;
      }
   );

   // shuffle the keys
   std::random_shuffle(keys.begin(), keys.end());

   // number of elements to pick
   num = std::min(num, m.size());

   std::vector<std::pair<char, int>> res;
   res.reserve(num);

   // pick num elements
   std::generate_n(std::back_inserter(res), num,
      [&keys, &m]() {
         auto it = m.find(keys.back());
         keys.pop_back();
         return *it;
      }
   );

   return res;
}

Идея состоит в том, чтобы случайным образом перемешать элементы в векторе, содержащие ключи ( т.е. keys). Поэтому вы перетасовываете ключи, которые сопоставляются с элементами на карте. Вы используете эти случайно перемешанные ключи для случайного получения элементов с карты.

---

^X или std::shuffle вставлено, поскольку std::random_shuffle устарело в C ++ 14 и удалено в C ++ 17.

Answer 2

std::sample - это C ++ 17, но вы можете легко реализовать его самостоятельно в C ++ 11. Например, для прямых итераторов (и std::map итератор удовлетворяет этому требованию) типичная реализация опирается на алгоритм выборочной выборки. Его описание можно найти в Vol.2. Кнута TAOCP , с.142.

Простейшая реализация:

template<class Forw_it, class Out_it, class URBG>
void sample(Forw_it first, Forw_it last, Out_it out, std::ptrdiff_t n, URBG&& g) {
    auto sz = std::distance(first, last);
    n = std::min(n, sz);

    while (n != 0) {
        std::uniform_int_distribution<std::ptrdiff_t> d(0, --sz);
        if (d(g) < n) {
            *out++ = *first;
            --n;
        }
        ++first;
    }
}

Пример использования:

std::map<char, int> values;
// ... assign values ...

std::vector<std::pair<char, int>> vec;
sample(values.begin(), values.end(), std::back_inserter(vec), 4, std::mt19937{});

for (auto p : vec)
    std::cout << p.first << ' ' << p.second << '\n';

Пример вывода:

b 30
e 90
f 100
g 120

Полная демонстрация