कुशलतापूर्वक n विकल्पों में से लंबाई कश्मीर के अगले परिवर्तन की गणना

Question

मैं करने की जरूरत है कुशलतापूर्वकn विकल्पों में से लंबाई k के अगले परिवर्तन की गणना। n विकल्पों से n की अगली क्रमपरिवर्तन की गणना करने के लिए विकिपीडिया a great algorithm सूचीबद्ध करता है।

सबसे अच्छी बात मैं के साथ कि एल्गोरिथ्म (या the Steinhaus–Johnson–Trotter algorithm) का उपयोग किया जाता है, और फिर बस केवल सूची के पहले k आइटम पर विचार, और फिर से दोहराने के लिए जब भी परिवर्तन सभी उस स्थिति से ऊपर हैं ऊपर आ सकते हैं।

प्रतिबंध:

• एल्गोरिथ्म वर्तमान क्रमचय से ज्यादा कुछ नहीं दिया अगले क्रमचय की गणना करना चाहिए। यदि इसे सभी क्रमिक क्रमों की एक सूची उत्पन्न करने की आवश्यकता है, यह बहुत अधिक स्मृति लेगा।
• यह केवल लंबाई का क्रमपरिवर्तन की गणना करने में सक्षम होना चाहिए n की k (इस जहां अन्य एल्गोरिथ्म विफल रहता है

गैर की कमी है:

• परवाह नहीं अगर यह in- है जगह है या नहीं
• मुझे परवाह नहीं है अगर यह lexographical क्रम में है, या उस बात के लिए किसी भी क्रम
• मुझे परवाह नहीं है बहुत ज्यादा पाठ्यक्रम के कारण अगली क्रमपरिवर्तन, कितनी कुशलता से गणना करता है, यह मुझे हर बार सभी संभावित लोगों की सूची बनाकर अगली क्रमपरिवर्तन नहीं दे सकता है।

Answer 1

आप दो भागो में बांटा इस समस्या को तोड़ सकते हैं:

1) आकार n का एक सेट से आकार k के सभी उप-समूहों का पता लगाएं।

2) प्रत्येक ऐसे सबसेट के लिए, k आकार के सबसेट के सभी क्रमपरिवर्तन खोजें।

संदर्भित विकिपीडिया लेख भाग 2 के लिए एक एल्गोरिदम प्रदान करता है, इसलिए मैं इसे दोहराना नहीं चाहूंगा। भाग 1 के लिए एल्गोरिदम बहुत समान है। । सरलता के लिए, मैं इसे "पूर्णांकों [0...n-1] की k आकार के सभी उप-समूहों को खोजने के लिए व्याख्या करेंगे

1) सबसेट [0...k-1]

2) अगले सबसेट पाने के लिए, एक सबसेट S दिया से शुरू करें:

2 ए) का पता लगाएं, छोटी से छोटी j ऐसी है कि j ∈ S ∧ j+1 ∉ S तो j == n-1, वहाँ कोई अगले सबसेट है;।। हमारा काम हो

2b) j प्रपत्र एक दृश्य की तुलना में कम तत्वों i...j-1 (चूंकि इनमें से कोई भी मूल्य गुम हो गया था, j न्यूनतम नहीं होगा)। यदि i 0 नहीं है, तो इन तत्वों को i-i...j-i-1 से बदलें। तत्व तत्व j+1 के साथ तत्व बदलें।