Jak losowo przetasować wartości na mapie?

Question

Mam std :: map z kluczem i wartości jako liczby całkowite. Teraz chcę losowo przetasować mapę, więc klawisze wskazują losowo inną wartość. Próbowałem random_shuffle, ale nie kompiluje. Zauważ, że nie próbuję przetasować klawiszy, co nie ma sensu dla mapy. Próbuję randomize wartości.

Mogłem przesłać wartości do wektora, przetasować je, a następnie skopiować. Czy istnieje lepszy sposób?

Answer 1

Cóż, używając tylko mapy myślę o tym: utwórz tablicę flag dla każdej komórki mapy, losowo generuj dwie liczby całkowite s.t. 0 < = i, j < rozmiar mapy; zamień je i oznacz te komórki jako zamienione. iterować dla wszystkich.
EDYCJA: tablica jest alokowana według rozmiaru mapy i jest tablicą lokalną.

Answer 2

Wątpię ...

Ale ... Dlaczego nie napisać krótki klasę, która ma 2 wektorów w. Posortowaną std::vector kluczy i std::random_shuffle d std::vector wartości? Wyszukaj klucz, używając std::lower_bound i użyj std::distance i std::advance, aby uzyskać wartość. Łatwo!

Bez zbytniego myślenia, powinna ona mieć podobną złożoność do std::map i być może lepszą lokalizację odniesienia.

Niektóre nietestowane i niedokończone kody, aby zacząć.

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()); 
} 

Answer 3

Złożoność propozycji jest O(N) (obie kopie i shuffle ma złożoność liniową), który wydaje się optymalna (patrząc na mniej elementów wprowadzi zakaz losowość do swojej Shuffle).

Jeśli chcesz wielokrotnie przetasować swoje dane, możesz zachować mapę typu <Key, size_t> (tj. Przysłowiowy poziom pośredni), która indeksuje się do std::vector<Value>, a następnie kilkakrotnie przetasowuje ten wektor. To oszczędza wszystkie kopie w zamian za nadmiar przestrzeni na przestrzeni O(N). Jeśli sam typ Value jest drogi, masz dodatkowe vector<size_t> indeksów do prawdziwych danych, w których tasujesz.

Dla wygody można zawrzeć map i vector w jednej klasie, która udostępnia funkcję składową shuffle(). Takie opakowanie musiałoby również ujawnić podstawowe funkcje wyszukiwania/wstawiania/usuwania mapy podkładu.

EDIT: Jak podkreślił @tmyklebu w komentarzach, utrzymując (surowe lub Smart) wskaźniki do danych wtórnych mogą podlegać iteratora unieważnieniu (np podczas wstawiania nowych elementów na końcu, który powoduje zdolność VECTOR do zmiany rozmiaru). Używanie indeksów zamiast wskaźników rozwiązuje problem "wstawiania na końcu". Ale pisząc klasę opakowania, upewnij się, że wstawienia nowych par klucz-wartość nigdy nie powodują "wstawień w środku" dla danych dodatkowych, ponieważ to również unieważniłoby indeksy. Bardziej niezawodnym rozwiązaniem byłoby użycie biblioteki Boost.MultiIndex, która została zaprojektowana specjalnie w celu umożliwienia wielu typów widoku nad strukturą danych.

Answer 4

Możesz nacisnąć wszystkie klawisze w numerze vector, przetasować numer vector i użyć go do zamiany wartości w map.

Oto przykład:

#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; 
} 

Answer 5

Jeśli chcesz przetasować mapę w miejscu, można zaimplementować własną wersję random_shuffle dla map. Rozwiązanie nadal wymaga umieszczenia klawiszy do wektora, która jest wykonywana przy użyciu transform poniżej:

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]]); 
} 

użyłem drand48()/srand48() jednolitej pseudo generator liczb losowych, ale można użyć, co jest najlepsze dla Ciebie.

Alternatywnie można przetasować v, a następnie odbudować map, takich jak:

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

Ale chciałem pokazać, że wdrażanie SHUFFLE na mapie w miejscu, nie jest zbyt uciążliwe.

Answer 6

Oto moje rozwiązanie przy użyciu std::reference_wrapper z C++ 11.

Najpierw zróbmy wersję std :: random_shuffle, która przetasuje odniesienia. Jest to mała modyfikacja wersja 1 z here: za pomocą metody get uzyskać dostęp do wartości odniesienia.

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()); 
    } 
} 

Teraz to proste:

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()); 
}