बिटवाइस पारी सी में हर संभव क्रमपरिवर्तन उत्पन्न करने के लिए

Question

संभव डुप्लिकेट:
Creating multiple numbers with certain number of bits set

मैं कुछ कोड है जिसके द्वारा एक सरणी में संख्या के प्रत्येक संभव संयोजन रखा जाएगा लिखने के लिए प्रयास कर रहा हूँ बिट्स को स्थानांतरित करना।

उदाहरण के लिए, मैं 3 बिट्स के सभी संभव संयोजनों को खोजने के लिए (जहां अधिकतम अंक के हो सकता है कर रहा है 6) सरणी शामिल करना चाहिए चाहता था:

000111 
001011 
001101 
001110 
010011 
010101 
010110 
011001 
011010 
011100 
100011

और इसी तरह ...

मैंने जो व्याख्या की है, जब अंतिम स्थिति बिट 1 है, तो हम संख्या 1 (x >> 1) को स्थानांतरित करते हैं और शुरुआत में 1 जोड़ते हैं। हालांकि, मुझे यकीन नहीं है कि बाकी को कैसे कोड करें। मैं इसे लिखने के लिए सी का उपयोग कर रहा हूँ।

इसके अलावा - जहां तक ​​मैं यह कह सकता हूं कि यह एक कोलेक्स अनुक्रम है, हालांकि, अगर मैं एक और अनुक्रम देता हूं तो मुझे सभी कान मिलेंगे जो मुझे एक ही अंत परिणाम देगा (के-बिट्स के सभी संभावित संयोजनों के साथ सरणी एन की बाधा)।

Answer 1

आप अनुक्रमों को पुन: उत्पन्न करके इसे हल कर सकते हैं।

हमें एक पुनरावर्ती समारोह f(int index, int bits, int number) कि बिट और bits की संख्या की वर्तमान index में ले जाएगा रखने के लिए बायां को परिभाषित करते हैं, और number अब तक उत्पन्न। फिर, आपके पास वर्तमान बिट को 1 या 0 तक सेट करने का विकल्प है, और वहां से रिकर्सिंग का विकल्प है।

कुल मिलाकर, समय जटिलता ओ (दृश्यों की संख्या), या हे (एन बी चुनें), जहां एन अंकों की संख्या है होना चाहिए और बी के लिए 1.

समारोह सेट बिट्स की संख्या है

void f(int index, int bits, int number) { 
    if (index == 0) { 
     if (bits == 0) { // all required bits have been used 
      emit_answer(number); // chuck number into an array, print it, whatever. 
     } 
     return; 
    } 

    if (index-1 >= bits) { // If we can afford to put a 0 here 
     f(index-1, bits, number); 
    } 

    if (bits > 0) { // If we have any 1s left to place 
     f(index-1, bits-1, number | (1 << (index-1))); 
    } 
} 

// to call: 
f(6, 3, 0); 

N,B = 6,3 के लिए उत्पादन तुम्हारा मैच, और क्रमबद्ध क्रम में है: कुछ इस तरह चला जाता है। काम करने के उदाहरण से लिंक: http://codepad.org/qgd689ZM

Answer 2

शायद अधिक कुशल तरीका है, लेकिन आप केवल संख्याओं के माध्यम से लूप कर सकते हैं और उन संख्याओं को अस्वीकार कर सकते हैं जिनके पास 3 की थोड़ी गिनती नहीं है? बिट गिनती के लिए this answer देखें।

Answer 3

किसी भी फैंसी रिकर्सन की आवश्यकता नहीं है। कुछ सरल गणित पर्याप्त होंगे (एक मूल्य से एक विभाजन जो हमेशा दो की शक्ति होगी) आवश्यक है।

 
    Function nextBits(ByVal prevVal As Integer) 
     Dim lsOne As Integer = ((prevVal - 1) And Not prevVal) + 1 
     Dim nextZero As Integer = (prevVal + lsOne) And Not prevVal 
     Dim lowBits As Integer = ((nextZero \ lsOne \ 2) - 1) 
     Return prevVal + lsOne + lowBits 
    End Function 

अच्छा और आसान।