सी ++ में इस फॉर-लूप गड़बड़ी से कैसे बचें?

Question

मुझे क्रमशः 1 से N से संख्याओं के सभी संभावित सेट प्रोग्राम करने की आवश्यकता है, बिना किसी क्रमिकता के पूर्णांक संख्या m।

के बाद से मैं नहीं जानता कि यह कैसे समझाने के लिए बेहतर यहाँ कुछ उदाहरण हैं:

के लिए m = 3

vector<vector<int>> box;  
int N = 5; 

for(int i = 1; i <= N; i++) { 
    for(int j = N; j >= i; j--) { 
     for(int k = N; k >= j; k--) { 
      vector<int> dummy; 
      dummy.push_back(i); 
      dummy.push_back(j); 
      dummy.push_back(k); 
      box.push_back(dummy); 
     } 
    } 
} 

यह पूरी तरह से ठीक काम करता है के लिए m = 2

vector<vector<int>> box;  
int N = 5; 

for(int i = 1; i <= N; i++) { 
    for(int j = N; j >= i; j--) { 
     vector<int> dummy; 
     dummy.push_back(i); 
     dummy.push_back(j); 
     box.push_back(dummy); 
    } 
} 

और परिणाम है क्या चाहिए मुझे। लेकिन जैसा कि पहले से ही उल्लेख किया गया है, m मनमाने ढंग से हो सकता है और मुझे इसे m = 37 या कभी भी लागू करने के लिए परेशान नहीं किया जा सकता है। N और m ज्ञात मूल्य हैं लेकिन प्रोग्राम चल रहा है, जबकि परिवर्तन। 37-फॉर-लूप की एक पंक्ति को लागू करने के लिए m = 37 मामले के लिए इसे लागू करने का एक बेहतर तरीका होना चाहिए। क्या कोई मेरी मदत कर सकता है? मैं दयालु हूं: \

संपादित करें: बेहतर तरीके से व्याख्या करने के लिए जो मैं यहां देख रहा हूं, कुछ और उदाहरण हैं।

के N = 5 और m = 4 कहते हैं, की तुलना में 1223 मेरे लिए एक उपयुक्त समाधान नहीं है चलो, 124 के बाद से यह कम करने के लिए है नहीं है। आइए मान लें कि मुझे पहले से ही 1223 एक समाधान के रूप में मिला है, मुझे 2123, 2213 या इस नंबर के किसी अन्य क्रमपरिवर्तन की आवश्यकता नहीं है।

संपादित 2: या यदि आप यहां एक और दृश्य (गणितीय?) समस्या फॉर्मूलेशन पसंद करते हैं तो आप जाते हैं।

आयाम m आयाम पर विचार करें। m 2 के साथ आप N आकार मैट्रिक्स के साथ छोड़े गए हैं। मैं विकर्ण सहित इस मैट्रिक्स के ऊपरी (या निचले) त्रिकोण की तलाश में हूं। आइए m = 3 पर जाएं, मैट्रिक्स एक 3 आयामी घन (या यदि आप चाहें तो टेंसर) बन जाता है, अब मैं ऊपरी (या निचले) टेट्राहेड्रॉन को विकर्ण-सादा समेत देख रहा हूं। 3 से अधिक आयामों के लिए मैं अति-विकर्ण-विमान सहित हाइपर-क्यूब के हाइपर-टेट्रैड्रॉन की तलाश में हूं।

Answer 1

http://howardhinnant.github.io/combinations.html

निम्नलिखित सामान्य एल्गोरिदम एक ग्राहक की अनुमति हर संयोजन या लंबाई एन, समय में आर मदों की एक अनुक्रम का permuation यात्रा करने के लिए।

उदाहरण उपयोग:

std::vector<std::vector<int>> box; 

std::vector<int> v(N); 
std::iota(begin(v), end(v), 1); 

for_each_combination(begin(v), begin(v) + M, end(v), [](auto b, auto e) { 
    box.emplace_back(b, e); 
    return false; 
}); 

ऊपर कोड सिर्फ एक उदाहरण के रूप में box में प्रत्येक संयोजन डालने से पता चलता है, लेकिन आप शायद वास्तव में ऐसा करने के लिए नहीं करना चाहती: यह सोचते हैं कि box बस एक मध्यस्थ है और कि आपका वास्तविक काम इसे कहीं और उपयोग करता है, आप मध्यस्थ से बच सकते हैं और केवल वही काम करते हैं जो आपको सीधे मज़ेदार के शरीर में चाहिए।

यहां दिए गए लिंक से कोड का उपयोग कर complete, working example है।

---

के बाद क्या आप चाहते हैं बस संयोजन के बजाय दोहराव के साथ संयोजन है। इस क्या कर रहा है की एक अच्छी चित्रण

template<typename Func> 
void for_each_combination_with_repetition(int categories, int slots, Func func) { 
    std::vector<int> v(slots + categories - 1); 
    std::iota(begin(v), end(v), 1); 

    std::vector<int> indices; 
    for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) { 
     indices.clear(); 
     int last = 0; 
     int current_element = 0; 

     for(;b != e; ++last) { 
      if (*b == last+1) { 
       indices.push_back(current_element); 
       ++b; 
      } else { 
       ++current_element; 
      } 
     } 
     func(begin(indices), end(indices)); 
     return false; 
    }); 
} 

विकिपीडिया article on combinations पता चलता है:: यहाँ for_each_combination() की चोटी पर इस को लागू करने का एक उदाहरण है यह (बिना दोहराव) संख्या [0 के सभी संयोजनों हो रही है, एन एम - 1) और फिर परिणामों में 'अंतराल' की तलाश में है। अंतराल एक तत्व की पुनरावृत्ति से अगले की पुनरावृत्ति के लिए संक्रमण का प्रतिनिधित्व करते हैं।

आपके द्वारा इस एल्गोरिदम में जाने वाले मज़ेदार को एक श्रेणी दी गई है जिसमें आपके द्वारा एकत्र किए जा रहे तत्वों वाले संग्रह में सूचकांक शामिल हैं। उदाहरण के लिए यदि आप {x, y} के सेट से तीन तत्वों के सभी सेट प्राप्त करना चाहते हैं, तो परिणाम आप चाहते हैं {{x, x, x}, {x, x, y}, {x, y, वाई}, {वाई, वाई, वाई}}, और यह एल्गोरिदम सूचकांक की श्रेणियों को क्रमबद्ध (क्रमबद्ध) सेट {x, y} में लौटकर दर्शाता है: {{0,0,0}, {0,0,1} , {0,1,1}, {1,1,1}}।

तो आम तौर पर इसका उपयोग करने के लिए आपके पास वेक्टर या कुछ तत्व होते हैं और इस एल्गोरिदम द्वारा उत्पादित श्रेणियों का उपयोग उस कंटेनर में इंडेक्स के रूप में करते हैं। हालांकि आपके मामले में, के बाद से तत्वों एन 1 से सिर्फ संख्या हैं आप सूचकांक सीधे एक सूचकांक के लिए एक जोड़कर उपयोग कर सकते हैं:

for_each_combination_with_repetition(N, M, [&](auto b, auto e) { 
    for(; b != e; ++b) { 
     int index = *b; 
     std::cout << index + 1 << " "; 
    } 
    std::cout << '\n'; 
}); 

Complete example

---

एक वैकल्पिक कार्यान्वयन वैक्टर लौट सकते हैं जो प्रत्येक श्रेणी की गणना का प्रतिनिधित्व करता है। जैसे पहले {{x, x, x}, {x, x, y}, {x, y, y}, {y, y, y}} परिणामों का प्रतिनिधित्व इस प्रकार किया जा सकता है: {{3,0} {2, 1}, {1,2}, {0,3}}। निर्माण करने के लिए कार्यान्वयन में संशोधन करना इस प्रतिनिधित्व के बजाय इस तरह दिखता है:

template<typename Func> 
void for_each_combination_with_repetition(int categories, int slots, Func func) { 
    std::vector<int> v(slots + categories - 1); 
    std::iota(begin(v), end(v), 1); 

    std::vector<int> repetitions(categories); 
    for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) { 
     std::fill(begin(repetitions), end(repetitions), 0); 

     int last = 0; 
     int current_element = 0; 

     for(;b != e; ++last) { 
      if (*b == last+1) { 
       ++repetitions[current_element]; 
       ++b; 
      } else { 
       ++current_element; 
      } 
     } 
     func(begin(repetitions), end(repetitions)); 
     return false; 
    }); 
} 

Answer 2

आप सभी सबसेट खोजने के लिए रिकर्सन का उपयोग कर सकते हैं। यह शायद शैलीगत सुधार किया जा सकता है, लेकिन यहां समस्या का शीघ्रता से ले रहा है:

std::vector<std::set<int>> subsets(std::vector<int> x) 
{ 
    if (x.size() == 0) 
     return { std::set<int>() }; 
    else 
    { 
     int last = x.back(); 
     x.pop_back(); 

     auto sets = subsets(x); 
     size_t n = sets.size(); 

     for (size_t i = 0; i < n; i++) 
     { 
      std::set<int> s = sets[i]; 
      s.insert(last); 
      sets.push_back(std::move(s)); 
     } 

     return sets; 
    } 
} 

यह प्रत्येक प्रत्यावर्तन कदम पर जवाब की संख्या को दोगुना: उम्मीद के रूप में उप-समूहों की संख्या, 2^है एन।

यदि आप चाहें तो std::vector के लिए std::set को प्रतिस्थापित कर सकते हैं।