जाँच हो रही है स्ट्रिंग की एक सूची श्रृंखलित जा सकता है अगर

Question

प्रश्न

एक समारोह bool chainable(vector<string> v), जो पैरामीटर के रूप में तार का एक सेट ले जाता है और true रिटर्न अगर वे श्रृंखलित हो सकता है को लागू करें। अगर पहले एक ही चरित्र दूसरे के साथ शुरू होता है, जैसे के साथ समाप्त होता दो तार श्रृंखलित जा सकता है:

ship->petal->lion->nick = true; 
ship->petal axe->elf = false; 

मेरे समाधान:

मेरे तर्क यह है कि अगर इसके chainable वहाँ केवल एक शुरुआत हो जाएगा और अंत जो मेल नहीं खाता है। तो मैं शुरुआत की एक सूची और अंत की एक सूची बनाते हैं। इस तरह।

starts:s,p,l,n 
ends: p,l,n,k 

अगर मैं आम तत्व निकालने के लिए, सूची में सबसे एक आइटम पर शामिल करना चाहिए। अर्थात् एस और के। यदि ऐसा है तो सूची श्रृंखला योग्य है। यदि सूची चक्रीय है, तो अंतिम सूचियां खाली हैं।

लेकिन मुझे लगता है कि मैं यहाँ कुछ मामलों याद आ रही है,

संपादित करें: ठीक है स्पष्ट रूप से मैं अपने समाधान में दोष था। क्या हम इसके लिए सर्वश्रेष्ठ एल्गोरिदम निष्कर्ष निकाल सकते हैं?

Answer 1

समस्या एक Eulerian path निर्देशित ग्राफ जिसका कोने पत्र के कम से कम एक के पहले या अंतिम पत्र के रूप में घटित हो रहा है में मौजूद रहने पर जाँच करने के लिए है आपूर्ति किए गए शब्द और जिनके किनारों को आपूर्ति किए गए शब्द हैं (प्रत्येक शब्द अपने पहले अक्षर से आखिरी पत्र है)।

रेखांकन में Eulerian रास्तों के अस्तित्व के लिए कुछ आवश्यक शर्तें:

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

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

अब महत्वपूर्ण बात यह है कि ये स्थितियां भी पर्याप्त हैं। कोई यह साबित कर सकता है कि किनारों की संख्या पर प्रेरण करके।

यह एक बहुत ही कुशल जांच करने के लिए अनुमति देता है:

• रिकॉर्ड सभी किनारों और कोने शब्द से प्राप्त के रूप में
• एक संघ खोजने संरचना/एल्गोरिथ्म का उपयोग ग्राफ
• रिकॉर्ड की जुड़ा घटक गिनती करने के लिए सभी कोने के लिए indegree - outdegree

number of components > 1 हैं या वहाँ (कम से कम) या |indegree - outdegree| > 1 साथ एक शीर्ष है वहाँ मीटर कर रहे हैं indegree != outdegree के साथ दो शीर्षकों से अयस्क, शब्द श्रृंखला योग्य नहीं हैं, अन्यथा वे हैं।

Answer 2

यहाँ एक मामले में जहां अपने एल्गोरिथ्म काम नहीं करता है:

ship 
pass 
lion 
nail 

आपका आरंभ और अंत सूचियों दोनों s, p, l, n हैं, लेकिन आप एक निरंतर सेट नहीं कर सकते हैं (आप प्राप्त दो चेन - ship->pass और lion->nail) ।

एक रिकर्सिव खोज शायद सबसे अच्छा होने जा रहा है - एक प्रारंभिक शब्द (1) चुनें, और, प्रत्येक शब्द जो इसका अनुसरण कर सकता है (2), (2) से शुरू होने वाली श्रृंखला बनाने की छोटी समस्या को हल करने का प्रयास करें। जिसमें (1) को छोड़कर सभी शब्द शामिल हैं।

Answer 3

अगर आप petal और lionpawn और label के साथ बदलें, आप अभी भी है:
starts:s,p,l,n
ends: p,l,n,k

तुम एल्गोरिथ्म अपने chainable का फैसला करता है, लेकिन वे नहीं कर रहे हैं।
समस्या यह है कि आप प्रत्येक शब्द के पहले और अंतिम अक्षरों को डिस्कनेक्ट कर रहे हैं।

एक पुनरावर्ती बैकट्रैकिंग या गतिशील प्रोग्रामिंग एल्गोरिदम इस समस्या को हल करना चाहिए।

Answer 4

seperatedly जांच करने के लिए "chainable है" और "cylcic"

है अगर यह चक्रीय यह chainable पहले होना चाहिए होने के लिए है। आप कुछ इस तरह कर सकता है:

if (IsChainable) 
{ 
    if (IsCyclic() { ... } 
} 

नोट: यदि आप "cylic" के लिए श्रृंखला के केवल प्रथम और अंतिम तत्व जाँच ऐसी बात है।

Answer 5

कुख्यात traveling salesman problem के समान नहीं है?

यदि आपके पास n तार हैं, तो आप उनमें से एक ग्राफ बना सकते हैं, जहां प्रत्येक नोड एक स्ट्रिंग से मेल खाता है।

• a और b chainable हैं स्ट्रिंग (। Resp नोड), तो आपको एक बढ़त a -> b वजन 1 साथ परिचय: आप किनारों निम्नलिखित तरीके का निर्माण।
• के लिए सभी unchainable तार (resp। नोड्स) a और b, आप एक बढ़त a -> b वजन n साथ परिचय।

फिर, अपने सभी स्ट्रिंग्स chainable (दोहराए बिना) कर रहे हैं और आप ग्राफ जिसका वजन 2n से कम है में एक इष्टतम TSP मार्ग पा सकते हैं केवल यदि।

नोट: आपकी समस्या वास्तव में टीएसपी से सरल है, क्योंकि आप हमेशा स्ट्रिंग चेनिंग को टीएसपी में बदल सकते हैं, लेकिन जरूरी नहीं कि अन्य तरीकों से।

Answer 6

यह aWe शब्दों के लिए एन (जी) = Σ और ई (जी) = a->e के साथ एक digraph जी पर विचार करके यूलरियन पथ समस्या में कमी से हल किया जा सकता है।

Answer 7

जैसा कि फिमुम्यू ने बताया, यह एक ग्राफ समस्या है। आपके पास (निर्देशित) किनारों के साथ तारों (शिखर) का एक सेट है। स्पष्ट रूप से, ग्राफ़ चेन करने योग्य होने के लिए connected होना चाहिए - यह जांचना आसान है। दुर्भाग्य से, इस से परे नियम एक छोटे से स्पष्ट नहीं कर रहे:

तार एक बार से अधिक इस्तेमाल किया जा सकता है, लेकिन लिंक नहीं है, तो समस्या एक Eulerian path, जो कुशलता से किया जा सकता है मिल रहा है कर सकते हैं। एक युलरियन पथ एक बार प्रत्येक किनारे का उपयोग करता है, लेकिन एक से अधिक बार शिखर का उपयोग कर सकता है।

// this can form a valid Eulerian path 
yard 
dog 
god 
glitter 

yard -> dog -> god -> dog -> glitter 

तार एक बार से अधिक नहीं किया जा सकता है, तो समस्या एक Hamiltonian path मिल रहा है। चूंकि हैमिल्टनियन पथ समस्या एनपी-पूर्ण है, इसलिए कोई सटीक कुशल समाधान ज्ञात नहीं है। बेशक, छोटे एन के लिए, दक्षता वास्तव में महत्वपूर्ण नहीं है और एक ब्रूट फोर्स समाधान ठीक काम करेगा।

हालांकि, चीजें काफी सरल नहीं हैं, क्योंकि इस समस्या के इनपुट के रूप में होने वाले ग्राफों का सेट सीमित है। उदाहरण के लिए, निम्नलिखित मान्य निर्देशित ग्राफ है (dot नोटेशन में) (*)।

digraph G { 
    alpha -> beta; 
    beta -> gamma; 
    gamma -> beta; 
    gamma -> delta; 
} 

हालांकि, इस ग्राफ इस पहेली के नियमों का उपयोग कर तार से निर्मित नहीं किया जा सकता: अल्फा और गामा के बाद से दोनों बीटा से कनेक्ट, वे एक ही चरित्र के साथ समाप्त होना चाहिए (मान लेते हैं वे अंत करते हैं 'x' के साथ), लेकिन गामाडेल्टा से भी कनेक्ट होता है, इसलिए डेल्टा भी 'x' से शुरू होना चाहिए। लेकिन डेल्टा 'x' से शुरू नहीं हो सकता है, क्योंकि अगर ऐसा होता है, तो alpha -> delta का किनारा होगा, जो मूल ग्राफ में नहीं है।

इसलिए, यह हैमिल्टनियन पथ समस्या के समान ही है, क्योंकि इनपुट का सेट अधिक प्रतिबंधित है। यह संभव है कि एक कुशल एल्गोरिदम स्ट्रिंग चेनिंग समस्या को हल करने के लिए मौजूद है भले ही कोई कुशल एल्गोरिदम हैमिल्टनियन पथ समस्या को हल करने के लिए मौजूद न हो।

लेकिन ... मुझे नहीं पता कि वह एल्गोरिदम क्या होगा। हो सकता है कि कोई और वास्तविक समाधान के साथ आएगा, लेकिन औसत समय में मुझे आशा है कि किसी को यह जवाब दिलचस्प लगेगा।

(*) यह हैमिल्टनियन पथ भी होता है: alpha -> beta -> gamma -> delta, लेकिन यह निम्न के लिए अप्रासंगिक है।

Answer 8

यहाँ इस iteratively करने के लिए एक साधारण प्रोग्राम है:

#include <string> 
#include <vector> 
#include <iostream> 

using std::vector; 
using std::string; 

bool isChained(vector<string> const& strngs) 
{ 
    if (strngs.size() < 2) return false;  //- make sure we have at least two strings 
    if (strngs.front().empty()) return false; //- make sure 1st string is not empty 

    for (vector<string>::size_type i = 1; i < strngs.size(); ++i) 
    { 
     string const& head = strngs.at(i-1); 
     string const& tail = strngs.at(i); 
     if (tail.empty()) return false; 
     if (head[head.size()-1] != tail[0]) return false; 
    } 

    return true; 
} 

int main() 
{ 
    vector<string> chained; 
    chained.push_back("ship"); 
    chained.push_back("petal"); 
    chained.push_back("lion"); 
    chained.push_back("nick"); 

    vector<string> notChained; 
    notChained.push_back("ship"); 
    notChained.push_back("petal"); 
    notChained.push_back("axe"); 
    notChained.push_back("elf"); 

    std::cout << (isChained(chained) ? "true" : "false") << "\n";  //- prints 'true' 
    std::cout << (isChained(notChained) ? "true" : "false") << "\n"; //- prints 'false' 

    return 0; 
}