कुशल कार्यक्रम मुद्रित करने के लिए/आकार 3 के सभी बढ़ती subsequences वापसी एक सरणी में

Question

की तरह एक सरणी

1, 6, 5, 2, 3, 4

हम

1 2 3 
1 3 4 
1 2 4 
2 3 4 

मुद्रित करने के लिए की जरूरत को देखते हुए

ऐसा करने का सबसे अच्छा तरीका क्या है? क्या यह गतिशील प्रोग्रामिंग है?

क्या ब्रूटफोर्स ओ (एन 3) से बेहतर करने का कोई बेहतर तरीका है? मुझे यकीन है कि वहाँ है।

कारण मैं कहता हूँ गतिशील प्रोग्रामिंग है, क्योंकि मैं की तरह

• के लिए '1'

  कुछ के रूप में देख सकते हैं (आकार 2 के subsequences के साथ सरणी के बाकी के उप समस्या के सभी परिणाम मुद्रित)।

• '2' (आकार 2 की subseqences के साथ सरणी के बाकी के उप समस्याओं के सभी परिणामों को मुद्रित)

के लिए

और इस तरह चले जाते हैं।

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

अच्छा, ये केवल यादृच्छिक विचार हैं। आप मुझे सही अपहरण के साथ सही कर सकते हैं।

ठीक है, प्रिंट करने पर मुझे सही करने दें, मुझे वापस आने वाले विभिन्न बढ़ते अनुक्रमों की आवश्यकता है। मेरा मुद्दा यह है कि, मुझे इन अनुक्रमों को सबसे कुशल तरीके से प्राप्त करने के लिए एक दृष्टिकोण खोजने की आवश्यकता है।

Answer 1

आप सरणी के माध्यम से चल सकते हैं और याद रख सकते हैं कि वर्तमान बिंदु तक कौन सा आंशिक अनुक्रम संभव है। प्रिंट और किसी भी दृश्यों कि लंबाई तक पहुँच 3.

उदाहरण भूल:

(1 6 5 2 3 4) 
^
remember ((1)) 

(1 6 5 2 3 4) 
    ^
remember ((1) (1 6) (6)) 

(1 6 5 2 3 4) 
    ^
remember ((1) (1 6) (6) (1 5) (5)) 

(1 6 5 2 3 4) 
     ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2)) 

(1 6 5 2 3 4) 
     ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (1 2 3) (2 3) (3)) 
print and forget (1 2 3) 
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3)) 

(1 6 5 2 3 4) 
      ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3) (1 4) (1 2 4) (2 4) 
      (1 3 4) (2 3 4) (3 4) (4)) 
print and forget (1 2 4) 
print and forget (1 3 4) 
print and forget (2 3 4) 
done. 

चुनौती याद subsequences के लिए एक उपयुक्त डेटा संरचना के चुनाव में झूठ बोलते हैं लगता है।

Answer 2

1. आदेश दिया जोड़े की एक सूची बनाएं (ए, बी) ऐसी है कि एक < ख और सूचकांक (क) < सूचकांक (ख)। ओ (एन^2)
2. ओ (एन^2log (एन)) में इस सूची को क्रमबद्ध करें (या तो ए या बी - कोई फर्क नहीं पड़ता)। डेटा संरचना के आधार पर ओ (nlog (n)) बनाया जा सकता है।सबसे खराब स्थिति O (n^3log (एन)), औसत मामले O (n^2log (एन))

Answer 3

में -

सूची में प्रत्येक तत्व के लिए, सभी मिलान खोजने के द्विआधारी खोज का उपयोग कर जोड़े का आदेश दिया सामान्यीकृत मामले आप दो बातों पर आधारित जटिलता की गणना करने के लिए है:

1- Count of input numbers (I will call it b) 
2- Length of output (I will call it d) 

एक सामान्यीकृत विधि है कि मैं के बारे में सोच सकते हैं, (एन^2) हे में समस्या के लिए एक अनुरूप ग्राफ के निर्माण के लिए है:

यदि एक बड़ी संख्या बियर एक छोटी संख्या के बाद आता है, एक छोटे से एक निर्देशित किनारे है।

अब लंबाई डी के सभी अनुक्रमों को खोजने के लिए, आपको प्रत्येक संख्या से शुरू करने और लंबाई के सभी पथ (डी -1) आउटपुट की आवश्यकता है।

यदि आप बीएफएस जैसे ट्रैवर्सल विधि का उपयोग करते हैं तो जटिलता ओ (डी एक्स (बी^(डी -1)) से कम होगी)।

हालांकि आप लंबाई डी के पथ खोजने के लिए आसन्न मैट्रिक्स गुणा का उपयोग कर सकते हैं, जो जटिलता को ओ ((डी -2) एक्स (बी^3) से कम कुछ कम कर देगा)। (आसन्न मैट्रिक्स की एनएच पावर आपको बताएगी कि प्रत्येक नोड से दूसरे की लंबाई के साथ कितने पथ मौजूद हैं)।

वर्ग मैट्रिक्स गुणा जटिलता को कम करने के लिए algorithms हैं।