एन तत्वों के साथ 1 डी सरणी के सभी के-विभाजन का आकलन करें?

Question

यह एक साधारण अनुरोध की तरह लगता है, लेकिन Google मेरा मित्र नहीं है क्योंकि "विभाजन" डेटाबेस और फाइल सिस्टम स्पेस में हिट का एक गुच्छा स्कोर करता है।

मुझे के उप-सरणी में एन मानों (एन स्थिर है) की सरणी के सभी विभाजनों की गणना करने की आवश्यकता है। उप-सरणी बस यही हैं - एक प्रारंभिक अनुक्रमणिका और समाप्ति सूचकांक। मूल सरणी का समग्र क्रम संरक्षित किया जाएगा।

उदाहरण के लिए

, एन = 4 और कश्मीर = 2 के साथ:

[ | a b c d ] (0, 4) 
[ a | b c d ] (1, 3) 
[ a b | c d ] (2, 2) 
[ a b c | d ] (3, 1) 
[ a b c d | ] (4, 0) 

और कश्मीर के साथ = 3:

[ | | a b c d ] (0, 0, 4) 
[ | a | b c d ] (0, 1, 3) 
    : 
[ a | b | c d ] (1, 1, 2) 
[ a | b c | d ] (1, 2, 1) 
    : 
[ a b c d | | ] (4, 0, 0) 

मैं बहुत यकीन है कि यह एक मूल समस्या नहीं है कर रहा हूँ (और नहीं, यह होमवर्क नहीं है), लेकिन मैं इसे प्रत्येक के < = एन के लिए करना चाहता हूं, और यह अच्छा होगा अगर बाद के पास (जैसे के बढ़ता है) ने पहले के परिणामों का लाभ उठाया।

यदि आपके पास कोई लिंक है, तो कृपया साझा करें।

Answer 1

पूर्व परिणामों का पुन: उपयोग करने के लिए (k के कम मूल्यों के लिए), आप रिकर्सन कर सकते हैं।

समापन सूचकांक की सूची के रूप में इस तरह के विभाजन के बारे में सोचें (किसी भी विभाजन के लिए इंडेक्स प्रारंभ करना अंतिम विभाजन का अंतिम सूचकांक या पहले के लिए 0 है)।

तो, partitionings के अपने सेट सिर्फ 0 और एन

तो k के बीच k गैर घटते पूर्णांकों के सभी सरणियों का एक सेट घिरा है कर रहे हैं, तो आप k नेस्टेड छोरों

for (i[0]=0; i[0] < N; i[0]++) { 
    for (i[1]=i[0]; i[1] < N; i[1]++) { 
    ... 
      for (i[10]=i[9]; i[10] < N; i[10]++) { 
       push i[0]==>i[10] onto the list of partitionings. 
      } 
    ... 
    } 
} 

के माध्यम से यह कर सकते हैं

यदि k असंबद्ध है, तो आप इसे पुनरावर्ती कर सकते हैं।

अनुक्रमित एस और ई द्वारा प्राप्त किया जाता के बीच k विभाजन का एक सेट:

• :

  • EFP एस और ई के बीच प्रत्येक मान के लिए "पहले विभाजन के अंत" लूपिंग EFP और S

  • उस सूची में प्रत्येक वेक्टर के लिए, उस वेक्टर में प्री-पेंड "ईएफपी" के बीच k-1 विभाजनों की एक सूची को रिकर्सिव रूप से खोजें।

  • परिणामी वेक्टर लंबाई k परिणाम की सूची में जोड़ा गया है।

कृपया ध्यान दें कि मेरा उत्तर प्रत्येक टुकड़ा की अंतिम-बिंदुओं की सूची तैयार करता है। यदि आप (जैसा कि आपका उदाहरण दिखाता है) प्रत्येक टुकड़े के LENGTHS की एक सूची चाहते हैं, तो आपको वर्तमान स्लाइस एंड से अंतिम टुकड़ा अंत को घटाकर लंबाई प्राप्त करने की आवश्यकता है।

Answer 2

प्रत्येक विभाजन को भागों को अलग करने वाले के -1 इंडेक्स द्वारा वर्णित किया जा सकता है। चूंकि आदेश संरक्षित है, इसलिए ये सूचकांक कम नहीं हो सकते हैं। यही है, आकार के -1 के सबसेट और आपके द्वारा खोजे जाने वाले विभाजनों के बीच सीधा पत्राचार है।

How to iteratively generate k elements subsets from a set of size n in java?

केवल शिकन है कि खाली भागों अनुमति दी जाती है, कई कट अंक मेल खाना सकता है, लेकिन:

आकार k-1 के सभी उप-समूहों से अधिक पुनरावृत्ति के लिए, आप सवाल की जांच कर सकते एक सबसेट में प्रत्येक सूचकांक में सबसे अधिक बार शामिल हो सकता है। आप की जगह थोड़ा एल्गोरिथ्म समायोजित करना होगा:

द्वारा

 processLargerSubsets(set, subset, subsetSize + 1, j + 1); 

 processLargerSubsets(set, subset, subsetSize + 1, j);