मानचित्र में मूल्यों को यादृच्छिक रूप से कैसे घुमाएं?

Question

मेरे पास एक std :: नक्शा दोनों कुंजी और मान पूर्णांक के रूप में है। अब मैं यादृच्छिक रूप से मानचित्र को घुमा देना चाहता हूं, इसलिए चाबियाँ यादृच्छिक रूप से एक अलग मान को इंगित करती हैं। मैंने random_shuffle की कोशिश की लेकिन यह संकलित नहीं है। ध्यान दें कि मैं चाबियों को घुमाने की कोशिश नहीं कर रहा हूं, जो किसी मानचित्र के लिए कोई समझ नहीं लेता है। मैं मूल्यों को यादृच्छिक करने की कोशिश कर रहा हूं।

मैं मूल्यों को वेक्टर में धक्का दे सकता हूं, उसे घुमा सकता हूं और फिर वापस कॉपी कर सकता हूं। क्या कोई बेहतर तरीका है?

Answer 1

ठीक है, केवल मानचित्र का उपयोग करके मुझे लगता है कि: मानचित्र के प्रत्येक कक्ष के लिए ध्वज सरणी बनाते हैं, यादृच्छिक रूप से दो पूर्णांक उत्पन्न करते हैं। 0 < = i, j < मानचित्र का आकार; उन्हें स्वैप करें और इन कोशिकाओं को स्वैप के रूप में चिह्नित करें। सभी के लिए पुनरावृत्त।
संपादित करें: सरणी मानचित्र के आकार द्वारा आवंटित की जाती है, और यह एक स्थानीय सरणी है।

Answer 2

मैं इसे शक ...

लेकिन ... क्यों एक त्वरित कक्षा में। एक हल कर चाबियों का std::vector 2 वैक्टर है और मूल्यों की एक std::random_shuffle घ 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 को एक कक्षा के अंदर encapsulate कर सकते हैं जो shuffle() सदस्य फ़ंक्शन का खुलासा करता है। इस तरह के एक आवरण को अंडरलिंग मानचित्र की मूल लुकअप/सम्मिलन/मिटा कार्यक्षमता का पर्दाफाश करने की आवश्यकता होगी।

संपादित: जैसा कि टिप्पणी में @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

आप जगह में नक्शा शफ़ल चाहते हैं, तो आप अपने map के लिए random_shuffle के अपने स्वयं के संस्करण को लागू कर सकते हैं:

यहाँ एक उदाहरण है। समाधान अभी भी एक वेक्टर, जो 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

सी ++ 11 के std::reference_wrapper का उपयोग करके मेरा समाधान यहां है।

सबसे पहले, चलिए std :: random_shuffle का एक संस्करण बनाते हैं जो संदर्भों को shuffles। संस्करण 1here से यह 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()); 
}