शब्द खोज गेम के लिए यादृच्छिक अक्षरों को चुनने के लिए एल्गोरिदम

Question

boggle-शब्द गेम के समान बना रहा है। उपयोगकर्ता इस तरह अक्षरों का एक ग्रिड दिया जाता है:

O V Z W X 
S T A C K 
Y R F L Q 

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

O V Z W X 
z e x o p 
Y R F L Q 

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

उदाहरण के लिए:

• तुम बस बेतरतीब ढंग से वर्णमाला से नया पत्र ले सकता है। यह अच्छी तरह से काम नहीं करता है।

• इसी प्रकार, मुझे यादृच्छिक रूप से चुनना पड़ा लेकिन स्क्रैबल से पत्र आवृत्तियों का उपयोग करने से अच्छा काम नहीं हुआ। यह स्क्रैबल में बेहतर काम करता है क्योंकि मुझे लगता है कि आप अक्षरों का उपयोग करने वाले आदेश के बारे में कम बाध्य हैं।

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

कुछ विचार मैं माना जाता है:

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

• किसी भी तरह से खोज करें कि वर्तमान ग्रिड पर कौन से शब्दों को वर्तनी दी जा सकती है, नए अक्षरों को वाइल्डकार्ड होने के लिए ले जाया जा सकता है। इसके बाद मैं वाइल्डकार्ड को अक्षरों से बदल दूंगा जो सबसे बड़े शब्दों को वर्तनी करने की इजाजत देता है। मुझे यकीन नहीं है कि आप इसे कुशलता से कैसे करेंगे।

किसी अन्य विचार की सराहना की जाती है। मुझे आश्चर्य है कि इस समस्या को हल करने का कोई आम तरीका है और अन्य शब्द गेम किस प्रकार उपयोग करते हैं।

संपादित करें: अब तक के महान उत्तरों के लिए धन्यवाद! मैं उल्लेख करना भूल गया, मैं वास्तव में कम स्मृति/सीपीयू आवश्यकताओं को संभवतः लक्षित कर रहा हूं, शायद मैं SOWPODS शब्दकोश (लगभग 250,000) का उपयोग करने जा रहा हूं और मेरा ग्रिड 6 x 6.

Answer 1

नहीं कर सकता इसके लिए एक पूर्व निर्धारित एल्गोरिदम के बारे में पता है, लेकिन ...

यूनिक्स में एक शब्दकोश फ़ाइल है, और मुझे लगता है कि अन्य प्लेटफार्मों पर शायद कुछ ऐसा ही उपलब्ध है (शायद जावा पुस्तकालयों में भी? - google it)। वैसे भी, वर्तनी परीक्षक फ़ाइलों का उपयोग करें।

एक शब्द का जादू करने के बाद यह निकलता है, आपके पास मौजूदा अक्षर और खाली रिक्त स्थान हैं।

1) प्रत्येक मौजूदा पत्र से, दाएं, बाएं, ऊपर, नीचे जाएं (आपको रिकर्सिव एल्गोरिदम को समझने की आवश्यकता होगी)। जब तक आप अब तक बनाई गई स्ट्रिंग शब्दकोष फ़ाइल में शब्दों के अंत से शब्दों की शुरुआत में या पीछे की ओर मिलती है, जारी रखें। जब आप रिक्त स्थान पर आते हैं, तो आपको आवश्यक अक्षरों की आवृत्ति की गणना करें। सबसे लगातार अक्षरों का प्रयोग करें।

यह किसी शब्द की गारंटी नहीं देगा क्योंकि आपने इसी समापन या शुरुआत की जांच नहीं की है, लेकिन मुझे लगता है कि एक संपूर्ण खोज से लागू करना और बहुत अच्छे परिणाम प्राप्त करना बहुत आसान होगा।

Answer 2

मुझे लगता है कि यह आप के लिए एक कदम अपने गंतव्य के लिए करीब मिल जाएगा:

खेल एक ही शब्द सूची है कि खिलाड़ी का उपयोग करेगा प्रयोग करने के लिए एक तेजी से solver लिखें: http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 3

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

इसके अलावा उच्चतम स्कोरिंग बोर्ड (यानी सबसे आसान बोर्ड) चुनने के बजाय आप विशेषज्ञों के लिए गेम को और अधिक कठिन बनाने के लिए अलग-अलग स्कोर सीमाएं प्राप्त कर सकते हैं।

Answer 4

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

Answer 5

This wordgame मैंने थोड़ी देर पहले थप्पड़ मार दिया, जो आपके वर्णन के समान ही व्यवहार करता है, अक्षरों का चयन करने के लिए अंग्रेजी आवृत्ति सारणी का उपयोग करता है, लेकिन पहले फैसला करता है कि एक स्वर या व्यंजन उत्पन्न करना है, जिससे मुझे स्वरों की एक निश्चित दर सुनिश्चित करने की अनुमति मिलती है बोर्ड। ऐसा लगता है कि यह काफी अच्छा काम करता है।

Answer 6

आपको एन-ग्रामिंग और मार्कोवियन मॉडल देखना चाहिए।

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

उदाहरण के लिए, मुझे पता है कि मेरे 1000 शब्दों (कुल में 4000 अक्षर) से अक्षर क्यू केवल 40 बार उपयोग किया जाता है। फिर मैं गणना करता हूं कि मेरे मार्कोव हैश टेबल का उपयोग करके संभावित अक्षरों का पालन करें।

उदाहरण के लिए, QU 100% समय होता है, इसलिए मुझे पता है कि क्यू को आपके आवेदन द्वारा यादृच्छिक रूप से चुना जाना चाहिए, मुझे यह सुनिश्चित करने की आवश्यकता है कि पत्र यू भी शामिल है। फिर, "I" पत्र का 50% समय और "ए" 25% बार और "ओ" समय का 25% उपयोग किया जाता है।

यह वास्तव में समझाने के लिए वास्तव में जटिल है और मैं शर्त लगाता हूं कि वहां अन्य व्याख्याएं हैं जो तब बेहतर होती हैं।

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

विकिपीडिया इसे वास्तव में बुरी तरह बताता है, इसलिए मैं इसका पालन नहीं करता।

इस मार्कोव जनरेटर पर एक नज़र डालें:

http://www.haykranen.nl/projects/markov/demo/

Answer 7

आप Jumble algorithm के इस Java implementation पर लग सकता है पत्र के सेट कि कई शब्दकोश शब्द को दूसरे स्थान पर रखना लगता है:

 
$ java -jar dist/jumble.jar | sort -nr | head 
11 Orang Ronga angor argon goran grano groan nagor orang organ rogan 
10 Elaps Lepas Pales lapse salep saple sepal slape spale speal 
9 ester estre reest reset steer stere stree terse tsere 
9 caret carte cater crate creat creta react recta trace 
9 Easter Eastre asteer easter reseat saeter seater staree teaser 
9 Canari Carian Crania acinar arnica canari carina crania narica 
8 leapt palet patel pelta petal plate pleat tepal 
8 laster lastre rastle relast resalt salter slater stelar 
8 Trias arist astir sitar stair stria tarsi tisar 
8 Trema armet mater metra ramet tamer terma trame 
...