Geek asks and answers

How to randomly mix values ​​on a map?

I have std :: map with key and value as integers. Now I want to randomly shuffle the map, so the keys indicate a different value at random. I tried random_shuffle, but it does not compile. Please note that I am not trying to shuffle the keys, which does not make sense for the card. I am trying to randomize values.

I could paste the values ​​into a vector, shuffle, and then copy back. Is there a better way?

+5
source share
6 answers

You can press all keys in vector, shuffle vectorand use it to replace the values ​​in map.

Here is an example:

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;
int myrandom (int i) { return std::rand()%i;}
int main ()
{
    srand(time(0));
    map<int,string> m;
    vector<int> v;
    for(int i=0; i<10; i++)
        m.insert(pair<int,string>(i,("v"+to_string(i))));

    for(auto i: m)
    {
        cout << i.first << ":" << i.second << endl;
        v.push_back(i.first);
    }
    random_shuffle(v.begin(), v.end(),myrandom);
    vector<int>::iterator it=v.begin();
    cout << endl;
    for(auto& i:m)
    {
        string ts=i.second;
        i.second=m[*it];
        m[*it]=ts;
        it++;
    }
    for(auto i: m)
    {
        cout << i.first << ":" << i.second << endl;
    }
    return 0;
}
+3
source

O(N) ( , ), ( ).

, <Key, size_t> (.. ), std::vector<Value>, . O(N) . Value , vector<size_t> , .

map vector , shuffle(). // underyling.

EDIT. @tmyklebu , (raw smart) (, , ). " ". - , - " " , . Boost.MultiIndex, , .

+2

, : , s.t. 0 <= i, j < ; . .
EDIT: .

0

...

... , 2 . std::vector std::random_shuffle d std::vector ? std::lower_bound std::distance std::advance, . !

, std::map , , .

, .

template <class Key, class T>
class random_map
{
public:
    T& at(Key const& key);
    void shuffle();
private:
    std::vector<Key> d_keys; // Hold the keys of the *map*; MUST be sorted.
    std::vector<T> d_values;
}

template <class Key, class T>
T& random_map<Key, T>::at(Key const& key)
{
    auto lb = std::lower_bound(d_keys.begin(), d_keys.end(), key);
    if(key < *lb) {
        throw std::out_of_range();
    }
    auto delta = std::difference(d_keys.begin(), lb);
    auto it = std::advance(d_values.begin(), lb);
    return *it;
}

template <class Key, class T>
void random_map<Key, T>::shuffle()
{
    random_shuffle(d_keys.begin(), d_keys.end());
}
0

, random_shuffle map. - , , transform:

typedef std::map<int, std::string> map_type;
map_type m;
m[10] = "hello";
m[20] = "world";
m[30] = "!";
std::vector<map_type::key_type> v(m.size());
std::transform(m.begin(), m.end(), v.begin(),
               [](const map_type::value_type &x){
                   return x.first;
               });
srand48(time(0));
auto n = m.size();
for (auto i = n-1; i > 0; --i) {
    map_type::size_type r = drand48() * (i+1);
    std::swap(m[v[i]], m[v[r]]);
}

drand48()/srand48() , , .

v, map, :

std::random_shuffle(v.begin(), v.end());
map_type m2 = m;
int i = 0;
for (auto &x : m) {
    x.second = m2[v[i++]];
}

, .

0

, std::reference_wrapper ++ 11.

First, let's create a version of std :: random_shuffle that shuffles the links. This is a small modification of version 1 of here : using the method getto go to the specified values.

template< class RandomIt >
void shuffleRefs( RandomIt first, RandomIt last ) {
    typename std::iterator_traits<RandomIt>::difference_type i, n;
    n = last - first;
    for (i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i].get(), first[std::rand() % (i+1)].get());
    }
}

Now easy:

template <class MapType>
void shuffleMap(MapType &map) {
    std::vector<std::reference_wrapper<typename MapType::mapped_type>> v;
    for (auto &el : map) v.push_back(std::ref(el.second));
    shuffleRefs(v.begin(), v.end());
}
0
source

More articles:


All Articles