algorithm - कुछ संख्याओं को बिट्स सेट के साथ बनाना




binary permutation (3)

आप संयोजन उत्पन्न करना चाहते हैं, यह विकिपीडिया लेख देखें

मुसीबत

मुझे 32 बिट नंबर बनाने की आवश्यकता है (हस्ताक्षरित या अहस्ताक्षरित कोई फर्क नहीं पड़ता, सबसे ऊंचा बिट कभी भी सेट नहीं किया जाएगा) और प्रत्येक संख्या में बिट्स सेट की एक निश्चित संख्या होनी चाहिए।

निष्क्रिय समाधान

शून्य की संख्या से शुरू करना सबसे आसान समाधान है लूप के भीतर संख्या अब एक की वृद्धि हुई है, बिट्स की संख्या गिना जाती है, अगर गिनती में वांछित मूल्य होता है, तो संख्या को सूची में संग्रहित किया जाता है, यदि न केवल लूप दोहराता है पर्याप्त संख्या पाए जाने पर पाश रोका गया है। बेशक यह सिर्फ ठीक काम करता है, लेकिन वांछित बिट्स की संख्या एक बार बहुत अधिक हो जाती है, लेकिन यह बेहद धीमी गति से होती है।

एक बेहतर समाधान

सबसे सरल संख्या (चलो कहना है) 5 बिट्स सेट संख्या है जहां पहले 5 बिट सेट हैं यह संख्या आसानी से बनाई जा सकती है किसी पाश के अंदर पहले बिट सेट हो जाता है और नंबर एक के द्वारा बाईं ओर स्थानांतरित किया जाता है यह लूप 5 गुना चलता है और मुझे पहले नंबर 5 बिट्स सेट मिला। संख्याओं के अगले दो जोड़े भी आसान हैं। अब हम 6 बिट चौड़ा होने के लिए संख्या का ढोंग करते हैं और सर्वोच्च सेट नहीं है। अब हम पहले शून्य बिट को सही स्थानांतरित करना शुरू कर देते हैं, इसलिए हमें 101111, 110111, 111011, 111101, 111110 मिलते हैं। हम इसे दोहरा सकते हैं और इस प्रक्रिया को दोहराकर दोहरा सकते हैं। 0111110, 1011110, 1101110, इत्यादि। हालांकि इस तरह की संख्या आवश्यक होने से ज्यादा तेज़ हो जाएगी, इस सरल दृष्टिकोण का उपयोग करते हुए हम 1010111 जैसी संख्याएं छोड़ देते हैं।

तो क्या सभी संभावित क्रमपरिवर्तनों का एक बेहतर तरीका है, एक सामान्य दृष्टिकोण है, जिसका उपयोग किया जा सकता है, चाहे कितने बिट्स अगले नंबर पर हों और चाहे कितने सेट बिट्स की हमें सेट की आवश्यकता हो?


आपको या तो फ़ैक्टोरैडिक परमिटेशन की आवश्यकता है (उस पर Google) या विकी के एल्गोरिदम में से एक


आप hackersdelight.org से बीट-ट्विडिंग हैक का उपयोग कर सकते हैं।

अपनी पुस्तक में उन्हें एक-बिट सेट की संख्या के साथ अगले उच्च संख्या प्राप्त करने के लिए कोड है।

यदि आप इसे अपने नंबर को बढ़ाने के लिए एक आदिम के रूप में उपयोग करते हैं तो आपको केवल एक प्रारंभिक बिंदु मिलना है। एन बिट्स सेट के साथ पहले नंबर प्राप्त करना आसान है। यह सिर्फ 2 ^ (एन -1) -1 है

आप सभी संभव संख्याओं के माध्यम से इसे बहुत तेज़ तरीके से पुनरावृति करेंगे।

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;

     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int bits = 2;
    int a = pow(2,bits) - 1;
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d\n", a);
       a = next_set_of_n_elements(a);
    }
  }






combinations