अक्षरों का सबसे बड़ा संभव आयत

Question

अक्षरों का सबसे बड़ा संभावित आयत खोजने के लिए एक प्रोग्राम लिखें, जैसे कि प्रत्येक पंक्ति एक शब्द (बाएं से दाएं) बनाती है और प्रत्येक कॉलम एक शब्द (ऊपर से नीचे) बनाता है।

मुझे यह दिलचस्प सवाल मिला। यह होमवर्क नहीं है, हालांकि यह ऐसा लगता है। (मैं स्कूल में नहीं हूँ)। मैं इसे मजाक के लिए कर रहा हूँ।

उदाहरण

से बिल्ली, कार, बंदर, एपीआई, प्रतिनिधि, टिप हम (जो एक वर्ग है) निम्नलिखित आयत मिलती है:

c a r 
a p e 
t i p 

मेरा प्रारंभिक विचार कुछ प्रकार के उपसर्ग पेड़ का निर्माण करना है ताकि मैं एक विशिष्ट स्ट्रिंग के साथ शुरू होने वाले सभी शब्दों को पुनर्प्राप्त कर सकूं। यह तब उपयोगी होगा जब हमारे पास पहले से 2 या अधिक शब्द हों (या तो ऊपर से नीचे या बाएं से दाएं पढ़ने के लिए) और हमें जोड़ने के लिए अगला शब्द ढूंढना होगा।

कोई अन्य विचार?

संपादित

इस घनाभ (3 डी आयत) के साथ किया जा सकता है?

क्या होगा अगर इसे विकर्णों पर वैध शब्द होना चाहिए (विचार क्रेडिट: user645466); इसके लिए अलगाव कैसे अनुकूलित किया जाएगा?

Answer 1

डी डी शब्दकोश को जाने दें। एम और एन ठीक करें। हम constraint satisfaction problem (सीएसपी) के रूप में एम × एन आयताकार खोजने की समस्या बना सकते हैं।

एक्स _{मैं, 1} है & hellip; एक्स _{मैं, एन} ∈ डी         और forall; मैं ∈ {1, & hellip ;, m}
एक्स _{1, जे} है & hellip; एक्स _{मी, जे} ∈ डी         और forall; j ∈ {1, & hellip ;, n}
एक्स _{i, j} ∈ {ए, है & hellip ;, जेड}         और forall; मैं ∈ {1, & hellip ;, m}, और forall; j ∈ {1, & hellip ;, n}

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

एक उदाहरण के रूप में, हम एक्स _1,1 = Q का चयन करके एक 3 × 3 ग्रिड शुरू हो सकता है।

Q?? 
??? 
??? 

एक अंग्रेजी शब्दकोश के साथ

, (स्क्रैबल से पहले “ शब्द ” में) x _1,2 और एक्स _2,1 है U के लिए केवल संभावना।

सीएसपी को हल करने की कला बैकट्रैकिंग और बाधा प्रचार के बीच संतुलन है। यदि हम बाधाओं का प्रचार नहीं करते हैं, तो हम केवल ब्रूट फोर्स का उपयोग कर रहे हैं। अगर हम पूरी तरह से बाधाओं का प्रचार करते हैं, तो हमें बैकट्रैक की आवश्यकता नहीं है, लेकिन एक प्रचार एल्गोरिदम जो स्वयं द्वारा एनपी-हार्ड समस्या हल करता है, शायद चलाने के लिए महंगा है।

इस समस्या में, प्रत्येक बैकट्रैकिंग नोड पर एक बड़े शब्दकोश के साथ काम करना महंगा होगा जब तक कि हमारे पास अच्छी डेटा संरचना समर्थन न हो। मैं एक ऐसे दृष्टिकोण की रूपरेखा तैयार करूंगा जो trie या DAWG का उपयोग अक्षरों के सेट की गणना करने के लिए जल्दी से करता है जिसके माध्यम से एक उपसर्ग एक पूर्ण शब्द तक फैलता है।

प्रत्येक बैकट्रैकिंग नोड पर, हमारे द्वारा असाइन किए गए चर के सेट को एक युवा झुकाव है। दूसरे शब्दों में, कोई वैरिएबल तब तक असाइन नहीं किया जाता है जब तक कि इसके ऊपर के चर और बाईं ओर असाइन नहीं किया जाता है। नीचे दिए गए आरेख में, . असाइन किए गए चर को इंगित करता है और * और ? असाइन किए गए चर को इंगित करता है।

.....* 
...*?? 
...*?? 
..*??? 
*????? 

चर चिह्नित * अगले के लिए उम्मीदवारों एक मूल्य आवंटित करने के लिए कर रहे हैं। प्रत्येक विकल्प को एक निश्चित चर चुनने के बजाय कई विकल्पों का लाभ यह है कि कुछ परिवर्तनीय क्रम दूसरों की तुलना में काफी बेहतर हो सकते हैं।

प्रत्येक * के लिए, त्रिभुज/डीएडब्ल्यूजी में दो लुकअप करें, एक क्षैतिज के लिए और एक लंबवत के लिए, और अगले अक्षरों के सेट के चौराहे की गणना करें। एक क्लासिक रणनीति उम्मीद में कम संभावनाओं के साथ चर का चयन करना है कि हम एक विरोधाभास तेजी से पहुंचते हैं। मुझे इस रणनीति को पसंद है क्योंकि यह स्वाभाविक रूप से prunes है जब शून्य संभावनाओं के साथ एक चर है और एक के साथ एक चर है जब स्वाभाविक रूप से प्रचार करता है। परिणामों को कैशिंग करके, हम प्रत्येक नोड का मूल्यांकन बहुत तेजी से कर सकते हैं।

Answer 2

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

1. शब्दकोश से एक शब्द चुनें, इसे X पर कॉल करें। यह मैट्रिक्स की पहली पंक्ति होगी।

2. जांचें कि X[1], X[2], ..., X[N] आपके द्वारा बनाई गई आसान सूची का उपयोग करके सभी मान्य एकल अक्षर उपसर्ग हैं। यदि वे हैं, तो चरण 3 पर जाएं; अन्यथा चरण 1 पर वापस जाएं।

3. शब्दकोश से एक शब्द चुनें, इसे Y पर कॉल करें। यह मैट्रिक्स की दूसरी पंक्ति होगी।

4. चेक कि X[1] Y[1], X[2] Y[2], ..., X[N] Y[N] सभी वैध डबल पत्र का उपयोग कर कि काम सूची आपके द्वारा किए गए उपसर्ग कर रहे हैं। यदि वे हैं, तो चरण 5 पर जाएं; अन्यथा 3. कदम तो इस शब्दकोश में अंतिम शब्द था, तो कदम वापस सभी रास्ते जाने के लिए वापस जाने 1.

   ...

   2 (एन -1)। शब्दकोश से एक शब्द चुनें, इसे Z पर कॉल करें।यह मैट्रिक्स की एनटी पंक्ति होगी।

   2 एन। जांचें कि X[1] Y[1] ... Z[1], X[2] Y[2] ... Z[2], ..., X[N] Y[N] ... Z[N] शब्दकोश में सभी शब्द हैं। यदि वे हैं, बधाई हो, आपने इसे किया है! अन्यथा चरण 2 (एन -1) पर वापस जाएं। यदि यह शब्दकोश में आखिरी शब्द था, तो चरण 2 (एन -3) पर वापस जाएं।

तर्क एक समय में एक पंक्ति शब्द की आयत का निर्माण करने, पंक्तियों के लिए शब्दों का चयन और उसके बाद जाँच उस स्तंभ शब्दों को पूरा किया जा सकता है। यह एक समय में एक पत्र जोड़ने से बहुत तेजी से प्रगति करेगा।

Answer 3

बनाएँ थैला [] एक ही लंबाई = सूचकांक के शब्द के लिए तो प्रयास की एक सरणी, प्रत्येक लंबाई के wordlist के लिए

Rectangle makeRectangle(length, height, rectangle) 
    { 
     if (length == rectangle.length()) check if complete and return; 
     checkIfPartialComplete - check columns for valid prefixes 
     for (i from 1 to grouplist[i-1]) 
     { 
      newRectangle = append word[i] to rectangle 
      return makeRectangle(l,h, rectangle with appended word) if not equal to null 
     } 
    } 


boolean checkPartial(int l, Trie trie) 
{ 
    for (int i =0 ; i < l; i++) 
    { 
     String col = getColumn(i); 
     if (!trie.contains(col)) 
     { 
      return false; 
     } 
    } 
    return true; 
} 
boolean checkComplete(int l, Bag<String> lengthGroup) 
{ 
    for (int i=0; i < l ; i++) 
    { 
     String col = getColumn(i); 
     if (!lengthGroup.contains(col)) 
     { 
      return false; 
     } 
    } 
    return true; 
}