क्रमबद्ध इसलिए तत्वों का अंतर एक सरणी एक [i] -एक [i + 1] <= एक [i + 1] -एक [i + 2]

Question

के बाद से मैं शुरू कर दिया, पिछले सप्ताह, करने की कोशिश कर मेरा मन उड़ा रहा है शर्त के आधार पर एन तत्वों की एक सरणी को क्रमबद्ध करें: 2 तत्वों के बीच का अंतर हमेशा अगले 2 तत्वों के बराबर या बराबर होता है। उदाहरण के लिए:

• {2, 7, 10, 4} क्योंकि (2 - ­7 = ­-5) < (7 - ­10 = -­3) < (10 - ­4 = 6)

• {4, 10, 7, 2} क्योंकि (4 - ­10 = -­6) < (10 - ­7 = ­3) < (7 - ­2 = 5)

एक समाधान मैं considere:

Α[4] = { 10, 2, 7, 4} 

ऐसा नहीं है कि सरणी इस तरह से पुन: व्यवस्थित करने के लिए संभव है घ बस सरणी फेरबदल किया गया था और हर बार की जाँच करता है, तो यह स्थिति, तत्वों की एक छोटी संख्या के लिए एक कुशल विधि के साथ सहमति व्यक्त की, लेकिन समय लेने या तत्वों की एक बड़ी संख्या के लिए भी असंभव है।

एक और छोरों के साथ सरणी के आसपास तत्वों को स्थानांतरित करने के लिए कोशिश कर रहा था, की आवश्यकताओं को पूरा करने के लिए फिर से उम्मीद कर, लेकिन फिर इस विधि बहुत समय लगता है और कभी-कभी संभव नहीं है।

एक एल्गोरिथ्म किसी भी परिणाम के लिए प्रतीत नहीं होता है की कोशिश कर रहा है, लेकिन वहाँ कुछ किया जाना चाहिए।

अग्रिम में आपका बहुत बहुत धन्यवाद।

Answer 1

ऐसा नहीं है कि के बाद से diffence बढ़ती होना चाहिए, किसी भी समाधान तत्व पहले बढ़ती क्रम में है और फिर गिरने के क्रम में होगा। दो "उपधाराओं" में से किसी एक की लंबाई 0 हो सकती है, इसलिए एक समाधान में सख्ती से बढ़ते या कड़ाई से गिरने वाले अनुक्रम शामिल हो सकते हैं। दो सेट, ए और बी खाली सेट अनुमति दी जाती है में

फूट डालो सेट:

निम्नलिखित कलन विधि किसी भी समाधान मिल जाएगा।

बढ़ते क्रम में बी को क्रमबद्ध करें और बी गिरने के क्रम में क्रमबद्ध करें।

जुटना दो क्रमबद्ध सेट: एबी

चेक, अगर आप एक समाधान है।

ए और बी

Answer 2

मैं सामान्य रूप से सिर्फ कोड प्रदान नहीं करते में सभी संभव डिवीजनों के लिए ऐसा करें, लेकिन इस सवाल का मुझे intrigued, तो यहाँ एक जानवर बल समाधान है, कि मिल सकता है आप शुरू कर दिया।

अवधारणा हमेशा धीमी रहेगी क्योंकि सूची में अलग-अलग तत्वों को क्रमबद्ध करने के लिए एक दूसरे से स्वतंत्र नहीं हैं, इसलिए उन्हें परंपरागत ओ (एन लॉग एन) एल्गोरिदम का उपयोग करके क्रमबद्ध नहीं किया जा सकता है। हालांकि, मतभेदों को इस तरह से हल किया जा सकता है, जो समाधान की जांच को सरल बनाता है, और प्रसंस्करण को गति देने के समानांतर में क्रमपरिवर्तनों की जांच की जा सकती है।

import os,sys 
import itertools 

def is_diff_sorted(qa): 
    diffs = [qa[i] - qa[i+1] for i in range(len(qa)-1)] 
    for i in range(len(diffs)-1): 
    if diffs[i] > diffs[i+1]: 
     return False 
    return True 

a = [2,4,7,10] 
#a = [1,4,6,7,20] 
a.sort() 
for perm in itertools.permutations(a): 
    if is_diff_sorted(perm): 
    print "Solution:",str(a) 
    break 

Answer 3

यह स्थिति भिन्नता से संबंधित है। पड़ोसी तत्वों के बीच (नकारात्मक) अंतर स्थिर सूचकांक के साथ स्थिर या बढ़ना होगा।-1 द्वारा हालत गुणा और आप प्राप्त

a[i+1]-a[i] => a[i+2]-a[i+1] 

या

तो 2 व्युत्पन्न 0 या नकारात्मक है, जो पहली व्युत्पन्न एक ही या नीचे की ओर बदलते रहने जैसा ही होता है हो गया है, उदाहरण के लिए एक सर्कल के ऊपरी भाग के भाग। इसका मतलब यह नहीं है कि पहले व्युत्पन्न को खुद को सकारात्मक या नकारात्मक शुरू करना है, बस यह कभी ऊपर नहीं बदलता है।

समस्या एल्गोरिदमिक रूप से यह है कि यह एक साधारण प्रकार नहीं हो सकता है, क्योंकि आप सूची के केवल 2 तत्वों की तुलना कभी नहीं करते हैं, आपको एक समय में तीन की तुलना करना होगा (i, i + 1, i + 2) ।

तो यादृच्छिक क्रमपरिवर्तनों से अलग एकमात्र चीज क्लास के उत्तर में दी गई है (मूल्य पहले बढ़ रहा है, तो बिल्कुल गिर रहा है), लेकिन उसकी पर्याप्त स्थिति नहीं है क्योंकि आपके पास सकारात्मक 2 व्युत्पन्न हो सकता है अपने दो सेट (बढ़ते/गिरने) में।

तो क्या यादृच्छिक शफल से कहीं अधिक तेज़ समाधान है? मैं केवल निम्नलिखित तर्क (क्लास के उत्तर के समान) के बारे में सोच सकता हूं। किसी दिए गए वेक्टर के लिए समाधान अधिक संभावना है यदि आप डेटा को पहले सेगमेंट में विभाजित करते हैं जो बढ़ रहा है या स्थिर (गिरने नहीं) और दूसरा जो गिर रहा है या स्थिर (बढ़ता नहीं जा रहा है) और न ही खाली है। संभवतः एक तर्क दिया जा सकता है कि दोनों खंडों में लगभग बराबर आकार होना चाहिए। बढ़ते खंड में डेटा होना चाहिए जो एक साथ निकट हो और गिरने वाले खंड में डेटा शामिल होना चाहिए जो आगे अलग है। तो कोई मतलब से शुरू हो सकता है, और उसके करीब के डेटा की तलाश कर सकता है, उन्हें पहले सेट पर ले जाया जा सकता है, फिर अधिक व्यापक रूप से स्थानांतरित डेटा की तलाश करें और उन्हें दूसरे सेट पर ले जाएं। तो एक हिस्टोग्राम मदद कर सकता है।

[4 7 से 10 2] -> diff [3 3 -8] -> 2diff [0 -11]

Answer 4

@ roadrunner66 विश्लेषण पर विस्तार, समाधान के दो सबसे छोटे तत्वों लेने के लिए है मूल सरणी, और उन्हें लक्ष्य सरणी में पहले और आखिरी बनाते हैं; दो अगले सबसे छोटे तत्वों को लें और उन्हें दूसरा और आखिरी-आखिरी बनाओ; तब तक जारी रखें जब तक सभी तत्व लक्ष्य में नहीं रखे जाते। ध्यान दें कि कौन सा बायीं तरफ जाता है, और कौन सा दाहिने ओर कोई फर्क नहीं पड़ता।

मूल सरणी को सॉर्ट करने से प्रक्रिया की सुविधा मिलती है (छोटे तत्वों को ढूंढना तुच्छ हो जाता है), इसलिए समय जटिलता O(n log n) है। अंतरिक्ष जटिलता O(n) है, क्योंकि इसे एक लक्षित सरणी की आवश्यकता है। अगर यह जगह में करना संभव है तो मुझे हाथ से पता नहीं है।

Answer 5

बैकट्रैकिंग एल्गोरिदम पर आधारित एक समाधान है।

1. गैर-बढ़ते क्रम में इनपुट सरणी सॉर्ट करें।
2. सरणी के मानों को दो सबसेट में विभाजित करना प्रारंभ करें: दोनों सबसेट्स में यह सबसे बड़ा तत्व डालें (यह "मध्य" तत्व होगा), फिर दूसरा सबसे बड़ा मध्यस्थ सबसेट में रखें।
3. अनुक्रमिक रूप से शेष तत्वों को या तो सबसेट में डाल दें। यदि यह "अंतर" स्थिति का उल्लंघन किए बिना नहीं किया जा सकता है, तो अन्य सबसेट का उपयोग करें। यदि दोनों सबसेट स्वीकार्य नहीं हैं, रोलबैक और पिछले निर्णय बदलते हैं।
4. चरण 3 पर उत्पादित सरणी में से एक को उलट दें और इसे अन्य सरणी के साथ संयोजित करें।

नीचे अजगर कार्यान्वयन (यह सही नहीं है, सबसे बुरा दोष पुनरावर्ती दिया गया है: जबकि प्रत्यावर्तन एल्गोरिदम उलटे पांव लौटने के लिए काफी आम है, इस विशेष एल्गोरिथ्म रैखिक समय में काम करने के लिए लगता है, और प्रत्यावर्तन बहुत बड़ी लिए अच्छा नहीं है इनपुट सरणी)।

def is_concave_end(a, x): 
    return a[-2] - a[-1] <= a[-1] - x 

def append_element(sa, halves, labels, which, x): 
    labels.append(which) 
    halves[which].append(x) 
    if len(labels) == len(sa) or split_to_halves(sa, halves, labels): 
    return True 
    if which == 1 or not is_concave_end(halves[1], halves[0][-1]): 
    halves[which].pop() 
    labels.pop() 
    return False 
    labels[-1] = 1 
    halves[1].append(halves[0][-1]) 
    halves[0].pop() 
    if split_to_halves(sa, halves, labels): 
    return True 
    halves[1].pop() 
    labels.pop() 

def split_to_halves(sa, halves, labels): 
    x = sa[len(labels)] 
    if len(halves[0]) < 2 or is_concave_end(halves[0], x): 
    return append_element(sa, halves, labels, 0, x) 
    if is_concave_end(halves[1], x): 
    return append_element(sa, halves, labels, 1, x) 

def make_concave(a): 
    sa = sorted(a, reverse = True) 
    halves = [[sa[0]], [sa[0], sa[1]]] 
    labels = [0, 1] 
    if split_to_halves(sa, halves, labels): 
    return list(reversed(halves[1][1:])) + halves[0] 

print make_concave([10, 2, 7, 4]) 

यह इस एल्गोरिथ्म का परीक्षण करने के लिए सेट एक अच्छा डेटा का उत्पादन करने के लिए आसान नहीं है: यादृच्छिक संख्या के मैदान सेट या तो इस एल्गोरिथ्म के लिए बहुत आसान है या किसी समाधान नहीं है। Here मैं एक सेट है कि "पर्याप्त मुश्किल है" एक साथ दो क्रमबद्ध सूचियों मिश्रण, प्रत्येक "अंतर" हालत संतोषजनक से उत्पन्न करने के लिए कोशिश की। फिर भी इस डेटा सेट को रैखिक समय में संसाधित किया जाता है। और मुझे नहीं पता कि इस डेटा एल्गोरिदम की अधिक से अधिक रैखिक समय जटिलता का प्रदर्शन करने वाले किसी भी डेटा सेट को कैसे तैयार किया जाए ...