如何隨機隨機洗牌地圖中的值？

Question

我有一個std :: map鍵和值作爲整數。現在我想隨機隨機洗牌，所以隨機鍵指向一個不同的值。我嘗試了random_shuffle，但它不能編譯。請注意，我並不試圖洗牌，這對地圖來說沒有任何意義。我試圖隨機化這些值。

我可以將值推入一個向量，洗牌，然後複製回來。有沒有更好的辦法？

Answer 1

那麼，只使用地圖我認爲： 爲地圖的每個單元格製作一個標誌數組，隨機生成兩個整數s.t. 0 < = i，j <地圖大小;交換它們並將這些單元格標記爲交換。迭代所有。
編輯：數組是由地圖的大小分配，並且是一個本地數組。

Answer 2

我對此表示懷疑......

可是......爲什麼不寫有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()); 
} 

Answer 3

將你的建議的複雜性是O(N)，（無論是副本和洗牌具有線性複雜性），這似乎是最佳的（看着更少的元素將引入非隨機性到您的洗牌）。

如果您想重複洗牌您的數據，您可以維護<Key, size_t>類型的映射（即間接性的諺語級別），該映射會索引到std::vector<Value>中，然後重複洗牌該向量。這爲您節省了所有的複製以換取空間開銷O(N)。如果Value類型本身很昂貴，那麼您可以在您進行混洗的真實數據中額外添加索引vector<size_t>。

爲了方便起見，您可以將map和vector封裝在一個暴露了shuffle()成員函數的類中。這樣的包裝也需要公開基本查找/插入/擦除功能的解除映射。

EDIT：由於在評論所指出@tmyklebu，保持（原材料或智能）指針輔助數據可在使所述載體的容量末端插入新元素時受到迭代器失效（例如調整大小）。使用索引而不是指針解決了「插入到底」的問題。但是在編寫包裝類時，需要確保插入的新鍵值對永遠不會導致次級數據「中間插入」，因爲這也會使索引無效。一個更強大的庫解決方案將使用Boost.MultiIndex，這是專門設計，允許多種類型的數據結構的查看。

Answer 4

您可以推動vector中的所有密鑰，對vector進行隨機洗牌並使用它交換map中的值。

下面是一個例子：

#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

如果你想洗牌到位地圖，你可以實現自己的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++]]; 
} 

但是，我想說明的地方在地圖上實現洗牌是不是過於沉重的負擔。

Answer 6

這是我使用C++ 11的std::reference_wrapper的解決方案。

首先，讓我們製作一個版本的std :: random_shuffle來洗牌引用。這是對版本1的一個小修改，從here：使用get方法獲得參考值。

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

現在很容易：

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