बीएसटी के इनपुट

Question

के संभावित क्रमपरिवर्तन मुझे एक स्ट्रिंग दी गई है, यानी "सीपीएचबीडीजेड"। एक BST करने के लिए डालने (इस क्रम में) पत्र से मेरा होगा:

C 
/\ 
B P 
/\ 
    H Z 
/
D 

अगर हम स्ट्रिंग के क्रम में "CBPHDZ" हम समान पेड़ मिल जाएगा बदल जाते हैं। और मुझे इनपुट स्ट्रिंग के सभी क्रमपरिवर्तनों को ढूंढना और सूचीबद्ध करना है जो समान बीएसटी प्रदान करते हैं। मैं उन क्रमिक क्रमों की गणना करने के तरीके के साथ आया लेकिन मैं वास्तव में उन्हें पाता हूं जो किसी भी एल्गोरिदम को नहीं समझ सकता।

Answer 1

मान लीजिए कि आप पेड़ को संतुलित करने के लिए कोई रोटेशन (आदि) नहीं कर रहे हैं, तो आप पेड़ की संरचना से एक उत्तर प्राप्त कर सकते हैं: नए नोड्स हमेशा मौजूदा नोड्स के वंशज के रूप में जोड़े जाते हैं, इसलिए किसी भी नोड में उच्च होता है पेड़ अपने ही वंशजों से पहले होना चाहिए, लेकिन अपने "साथियों" (जो कुछ भी उसके माता-पिता और न ही वंशज है) के साथ इच्छानुसार पुन: व्यवस्थित किया जा सकता है।

उदाहरण के लिए, चूंकि आपके पास पेड़ की जड़ के रूप में C है, C स्ट्रीम से पढ़ा गया पहला आइटम होना चाहिए। चूंकि इसके वंशज B और P हैं, इसलिए इनपुट में अगला आइटम उन दोनों में से एक होना था। B में कोई वंशज नहीं है, लेकिन P में दो: H और Z हैं, इसलिए उन्हें P के बाद पढ़ना पड़ा, लेकिन B के संबंध में किसी भी क्रम में हो सकता है। इसी तरह, ZH और D के संबंध में किसी भी क्रम में हो सकता है, लेकिन HD से पहले होना चाहिए।

संपादित करें: उन सभी क्रमपरिवर्तनों को उत्पन्न करने के लिए, प्रोलॉग का उपयोग करने के लिए एक सरल (धोखाधड़ी) तरीका होगा। असल में, आप उस निर्भरताओं को "तथ्यों" के रूप में एन्कोड करते हैं, और यह उन तथ्यों को फिट करने वाले सभी क्रमिक क्रम उत्पन्न करेगा। वास्तव में (कोई इरादा नहीं है), यह प्रोलॉग क्या करता है/इसका विवरण है।

इसे अपने आप में करना, शायद आप अधिकतर नौकरी को बार-बार करना चाहते हैं। एक वैध आदेश एक जड़ है जिसके बाद उसके वंशजों के वैध आदेशों के किसी भी अंतःकरण से होता है।

जहां तक ​​इंटरलिविंग करना है, आप (उदाहरण के लिए) बाएं उप-पेड़ के एक वैध क्रम और दाएं उपट्री के एक वैध क्रम उत्पन्न करेंगे। शुरुआत में बाएं उप-पेड़ से सभी वस्तुओं के साथ उन्हें एक सरणी में रखो, और अंत में दाएं उप-पेड़ के सभी लोग। प्रदर्शन के लिए, मान लीजिए कि पेड़ में A भी शामिल है (B के वंशज के रूप में आप दिखाते हैं)। सही करने के लिए सरणी पार

B A P H Z D 

तो हम छोड़ दिया उप पेड़ से पिछले आइटम से प्रारंभ करें, और "सैर" प्रत्येक, एक पैदा: एक सरणी में, हमारे उप पेड़ से हमारे डेटा लगेगा की तरह नई क्रमचय हर बार:

B P A H Z D 
P B A H Z D 
B P H A Z D 
P B H A Z D 
P H B A Z D 
[ ... ]  

बाईं उप पेड़ से प्रत्येक वैध आदेश के लिए, आप और सही उप पेड़ से प्रत्येक वैध आदेश के साथ इन सभी interleavings क्या करने की जरूरत है (यह माता पिता पर लौटने, जो होगा ऐसा ही करने)।

Answer 2

अजगर में,

tree = { 
    'C' : ['B', 'P'], 
    'P' : ['H','Z'], 
    'H' : ['D']} 

def f(tree, ready): 
    if not ready: 
     return [[]] 
    else: 
     rv = [] 
     for r in ready: 
      for rest in f(tree, 
          [n for n in ready if r != n] + tree.get(r, [])): 
       rv.append([r] + rest) 
     return rv 

for o in f(tree, 'C'): 
    print ''.join(o)