Cách ngẫu nhiên trộn các giá trị trong bản đồ?

Question

Tôi có một std :: map với cả khóa và giá trị dưới dạng số nguyên. Bây giờ tôi muốn trộn ngẫu nhiên bản đồ, vì vậy các khóa trỏ đến một giá trị khác ngẫu nhiên. Tôi đã thử random_shuffle nhưng nó không biên dịch. Lưu ý rằng tôi không cố gắng xáo trộn các phím, điều này không có ý nghĩa gì đối với bản đồ. Tôi đang cố gắng để ngẫu nhiên các giá trị.

Tôi có thể đẩy giá trị vào vectơ, trộn và sao chép lại. Có cách nào tốt hơn?

Answer 1

Vâng, chỉ sử dụng bản đồ tôi nghĩ về điều đó: tạo một mảng cờ cho mỗi ô của bản đồ, tạo ngẫu nhiên hai số nguyên s.t. 0 < = i, j < kích thước bản đồ; trao đổi chúng và đánh dấu các ô này là hoán đổi. lặp lại cho tất cả.
EDIT: mảng được phân bổ theo kích thước của bản đồ và là một mảng cục bộ.

Answer 2

tôi nghi ngờ nó ...

Nhưng ... Tại sao không viết một lớp nhanh chóng mà có 2 vectơ trong. Một sắp xếp std::vector các phím và một std::random_shuffle d std::vector các giá trị? Tìm khóa bằng cách sử dụng std::lower_bound và sử dụng std::distance và std::advance để nhận giá trị. Dễ dàng!

Nếu không suy nghĩ quá sâu, điều này cần phải có độ phức tạp tương tự như std::map và có thể là địa phương tham chiếu tốt hơn.

Một số mã chưa được kiểm tra và chưa hoàn thành để giúp bạn bắt đầu.

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

Sự phức tạp của đề xuất của bạn là O(N), (cả bản và shuffle có độ phức tạp tuyến tính) mà dường như tối ưu (nhìn vào các yếu tố ít hơn sẽ giới thiệu phi ngẫu nhiên vào shuffle của bạn).

Nếu bạn muốn lặp lại nhiều lần dữ liệu, bạn có thể duy trì bản đồ loại <Key, size_t> (tức là mức độ gián đoạn ngôn ngữ) chỉ mục thành std::vector<Value> và sau đó chỉ cần lắc nhanh vectơ đó. Điều đó giúp bạn tiết kiệm tất cả việc sao chép để đổi lấy chi phí không gian O(N). Nếu chính loại Value đắt tiền, bạn có thêm vector<size_t> chỉ số vào dữ liệu thực mà bạn thực hiện việc xáo trộn.

Vì lợi ích thuận tiện, bạn có thể đóng gói map và vector bên trong một lớp hiển thị hàm shuffle() thành viên. Một trình bao bọc như vậy cũng cần phải trưng ra chức năng tra cứu/chèn/xóa cơ bản của bản đồ chưa hoàn thiện.

EDIT: Như đã chỉ ra bởi @tmyklebu trong các ý kiến, duy trì (sống hoặc thông minh) con trỏ đến dữ liệu thứ cấp có thể bị áp dụng iterator huỷ bỏ hiệu lực (ví dụ như khi chèn các yếu tố mới vào cuối gây ra năng lực của vector để được thay đổi kích thước). Sử dụng các chỉ mục thay vì con trỏ giải quyết vấn đề "chèn ở cuối". Nhưng khi viết lớp trình bao bọc, bạn cần đảm bảo chèn các cặp khóa-giá trị mới không bao giờ gây ra "chèn ở giữa" cho dữ liệu phụ của bạn vì điều đó cũng sẽ làm mất hiệu lực các chỉ mục. Một giải pháp thư viện mạnh mẽ hơn sẽ là sử dụng Boost.MultiIndex, được thiết kế đặc biệt để cho phép nhiều loại chế độ xem qua cấu trúc dữ liệu.

Answer 4

Bạn có thể đẩy tất cả các phím trong một vector, phát ngẫu nhiên vector và sử dụng nó để hoán đổi các giá trị trong map.

Dưới đây là một ví dụ:

#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

Nếu bạn muốn shuffle bản đồ tại chỗ, bạn có thể thực hiện phiên bản của riêng bạn random_shuffle cho map của bạn. Các giải pháp vẫn đòi hỏi đặt các phím vào một vector, được thực hiện dưới đây sử dụng 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]]); 
} 

tôi đã sử dụng drand48()/srand48() cho một bộ đồng phục giả bộ tạo số ngẫu nhiên, nhưng bạn có thể sử dụng bất cứ điều gì là tốt nhất cho bạn.

Ngoài ra, bạn có thể xáo trộn v, và sau đó xây dựng lại các map, chẳng hạn như:

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

Nhưng, tôi muốn để minh họa rằng thực hiện ngẫu nhiên trên bản đồ tại chỗ là không quá nặng nề.

Answer 6

Đây là giải pháp của tôi sử dụng std::reference_wrapper trong C++ 11.

Trước tiên, chúng ta hãy tạo một phiên bản std :: random_shuffle để thay đổi tham chiếu. Đây là một sửa đổi nhỏ của phiên bản 1 từ here: sử dụng phương thức get để truy cập các giá trị được tham chiếu.

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

Bây giờ thật dễ dàng:

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