scrambled अक्षरों में शब्दों के लिए कुशल शिकार

Question

मुझे लगता है कि आप इसे स्क्रैबल शैली की समस्या के रूप में वर्गीकृत कर सकते हैं, लेकिन यूके टीवी क्विज़ शो काउंटडाउन का उल्लेख करने वाले किसी मित्र के कारण यह शुरू हो गया। शो में विभिन्न दौरों में प्रतिभागियों को पत्रों का एक तंग सेट प्रस्तुत किया जाता है और उन्हें सबसे लंबे समय तक शब्द के साथ आना पड़ता है। मेरा एक दोस्त जिसका उल्लेख "रायपवेन" था।

काफी कम क्रम में मैंने पाइथन में इस समस्या को संभालने के लिए कुछ हद तक चाबुक लगाया, पीईएन्चेंट का उपयोग डिक्शनरी लुक-अप को संभालने के लिए किया, हालांकि मुझे लगता है कि यह वास्तव में उन सभी को स्केल नहीं कर सकता है।

#!/usr/bin/python 

from itertools import permutations 
import enchant 
from sys import argv 

def find_longest(origin): 
    s = enchant.Dict("en_US") 
    for i in range(len(origin),0,-1): 
     print "Checking against words of length %d" % i 
     pool = permutations(origin,i) 
     for comb in pool: 
      word = ''.join(comb) 
      if s.check(word): 
       return word 
    return "" 

if (__name__)== '__main__': 
    result = find_longest(argv[1]) 
    print result 

यह एक 9 पत्र उदाहरण पर ठीक है जैसे वे इस शो में उपयोग करते हैं, 9 भाज्य = 362,880 और 8 भाज्य = 40,320:

यहाँ मैं वर्तमान में पड़ता है। उस पैमाने पर भी अगर उसे सभी संभावित क्रमिकताओं और शब्द की लंबाई की जांच करनी पड़ेगी तो यह बहुत से नहीं है।

हालांकि एक बार जब आप 14 वर्णों तक पहुंचे तो 87,178,291,200 संभावित संयोजन हैं, जिसका अर्थ है कि आप भाग्य पर निर्भर हैं कि एक 14 चरित्र शब्द जल्दी से पाया जाता है।

ऊपर दिए गए शब्द के साथ यह मेरी मशीन को "reawaken" खोजने के लिए 12 1/2 सेकंड के बारे में ले रहा है। 14 चरित्र scrambled शब्दों के साथ हम सभी संभव 14 चरित्र क्रमपरिवर्तन की जांच के लिए 23 दिनों के पैमाने पर बात कर सकते हैं।

क्या इसे संभालने का कोई और अधिक प्रभावी तरीका है?

Answer 1

पत्र के साथ his answer से Jeroen Coupé विचार का कार्यान्वयन गिनती:

from collections import defaultdict, Counter 


def find_longest(origin, known_words): 
    return iter_longest(origin, known_words).next() 

def iter_longest(origin, known_words, min_length=1): 
    origin_map = Counter(origin) 
    for i in xrange(len(origin) + 1, min_length - 1, -1): 
     for word in known_words[i]: 
      if check_same_letters(origin_map, word): 
       yield word 

def check_same_letters(origin_map, word): 
    new_map = Counter(word) 
    return all(new_map[let] <= origin_map[let] for let in word) 

def load_words_from(file_path): 
    known_words = defaultdict(list) 
    with open(file_path) as f: 
     for line in f: 
      word = line.strip() 
      known_words[len(word)].append(word) 
    return known_words 

if __name__ == '__main__': 
    known_words = load_words_from('words_list.txt') 
    origin = 'raepkwaen' 
    big_origin = 'raepkwaenaqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnm' 
    print find_longest(big_origin, known_words) 
    print list(iter_longest(origin, known_words, 5)) 

आउटपुट (मेरे छोटे 58000 शब्दों के लिए dict):

counterrevolutionaries 
['reawaken', 'awaken', 'enwrap', 'weaken', 'weaker', 'apnea', 'arena', 'awake', 
'aware', 'newer', 'paean', 'parka', 'pekan', 'prank', 'prawn', 'preen', 'renew', 
'waken', 'wreak'] 

नोट्स:

• यह सरल कार्यान्वयन है अनुकूलन के बिना।

• words_list.txt - लिनक्स पर /usr/share/dict/words हो सकता है।

अद्यतन

मामले में हम केवल एक बार शब्द खोजने की जरूरत है, और हम लंबाई, उदा के अनुसार क्रमबद्ध शब्दों के साथ शब्दकोश है इस स्क्रिप्ट द्वारा:

with open('words_list.txt') as f: 
    words = f.readlines() 
with open('words_by_len.txt', 'w') as f: 
    for word in sorted(words, key=lambda w: len(w), reverse=True): 
     f.write(word) 

हम स्मृति के लिए पूर्ण dict लोड किए बिना सबसे लंबा शब्द पा सकते हैं:

from collections import Counter 
import sys 


def check_same_letters(origin_map, word): 
    new_map = Counter(word) 
    return all(new_map[let] <= origin_map[let] for let in word) 

def iter_longest_from_file(origin, file_path, min_length=1): 
    origin_map = Counter(origin) 
    origin_len = len(origin) 
    with open(file_path) as f: 
     for line in f: 
      word = line.strip() 
      if len(word) > origin_len: 
       continue 
      if len(word) < min_length: 
       return 
      if check_same_letters(origin_map, word): 
       yield word 

def find_longest_from_file(origin, file_path): 
    return iter_longest_from_file(origin, file_path).next() 

if __name__ == '__main__': 
    origin = sys.argv[1] if len(sys.argv) > 1 else 'abcdefghijklmnopqrstuvwxyz' 
    print find_longest_from_file(origin, 'words_by_len.txt') 

Answer 2

आप क्रमपरिवर्तन करने से बचना चाहते हैं। आप गिन सकते हैं कि दोनों तारों में एक वर्ण कितनी बार प्रकट होता है (मूल स्ट्रिंग और शब्दकोश से एक)। शब्दकोश के सभी शब्दों को खारिज करें जहां वर्णों की आवृत्ति समान नहीं है।

तो शब्दकोश से एक शब्द की जांच करने के लिए आपको अधिकतम MAX (26, n) समय पर वर्णों की गणना करने की आवश्यकता होगी।

Answer 3

1. शब्दकोष (शब्द), शब्द जोड़े के रूप में शब्दकोश को पूर्व-पार्स करें। (उदाहरण के लिए giilnstu, linguist)
2. शब्दकोश फ़ाइल को सॉर्ट करें।

फिर, जब आप पत्र का एक सेट के लिए खोज रहे हैं:

1. द्विआधारी खोज पत्र आपके पास, पत्र छँटाई पहले के लिए शब्दकोश।

आपको प्रत्येक शब्द की लंबाई के लिए इसे अलग से करने की आवश्यकता होगी।

संपादित करें: कहना चाहिए कि आप लक्ष्य शब्द की लंबाई (range(len(letters), 0, -1)) की क्रमबद्ध पत्र के सभी अद्वितीय संयोजन के लिए खोज कर रहे हैं

Answer 4

1. का निर्माण अपने शब्दकोश से trie (prefix tree)। आप इसे कैश करना चाहते हैं।
2. इस यात्रा पर चलें और उन सभी शाखाओं को हटाएं जो आपके अक्षरों के बैग को फिट नहीं करते हैं।

इस बिंदु पर, आपका trie आपके शब्दकोश में सभी शब्दों का प्रतिनिधित्व है जिसे आपके अक्षरों के बैग से बनाया जा सकता है।

1. बस ले लंबे समय तक एक (रों) :-)

संपादित करें: आप भी एक DAGW (Directed Acyclic Word Graph) उपयोग कर सकते हैं जो कम कोने होगा। हालांकि मैंने इसे नहीं पढ़ा है, इस विकिपीडिया लेख में The World's Fastest Scrabble Program का लिंक है।

Answer 5

10 अक्षरों से अधिक लंबे शब्दों की तलाश करते समय आप शब्दों पर फिर से प्रयास करने की कोशिश कर सकते हैं (मुझे लगता है कि 10 अक्षरों वाले इतने सारे शब्द नहीं हैं) जो 10 अक्षरों से अधिक हैं और जांचें कि आपके सेट में अक्षरों की आवश्यकता है।

समस्या यह है कि आपको उन सभी लेन (शब्द)> = 10 शब्दों को पहले ढूंढना होगा।

तो, मैं क्या करूँगा: शब्दकोश पढ़ने के दौरान शब्दों को 2 श्रेणियों में विभाजित करें: शॉर्ट्स और लम्बे। आप प्रत्येक संभावित क्रमपरिवर्तन पर पुनरावृत्ति करके शॉर्ट्स को संसाधित कर सकते हैं। इससे पहले कि आप इसे फिर से चालू करके लंबे समय तक संसाधित कर सकें और जांच कर सकें कि वे संभव हैं।

बेशक दोनों पथों के लिए कई अनुकूलन संभव हैं।

Answer 6

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

$ python longest.py rasdaddea aosddna raepkwaen 
rasdaddea --> sadder 
aosddna --> soda 
raepkwaen --> reawaken 

आप अधिक विवरण और कम से विपर्यय मामले का पूरी तरह से स्पष्टीकरण प्राप्त कर सकते हैं: http://mostlyhighperformance.blogspot.com/2012/01/generating-anagrams-efficient-and-easy.html

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

import sys 


def nextprime(x): 
    while True: 
     x += 1 
     for pot_fac in range(2,x): 
      if x % pot_fac == 0: 
       break 
     else: 
      return x 

def prime_generator(): 
    '''Returns a generator that produces the next largest prime as 
    compared to the one returned from this function the last time 
    it was called. The first time it is called it will return 2.''' 
    lastprime = 1 
    while True: 
     lastprime = nextprime(lastprime) 
     yield lastprime 


# Assign prime numbers to each lower case letter 
gen = prime_generator() 
primes = dict([ (chr(x),gen.next()) for x in range(ord('a'),ord('z')+1) ]) 


product = lambda x: reduce(lambda m,n: m*n, x, 1) 
make_key = lambda x: product([ primes[y] for y in x ]) 


try: 
    words = open('words').readlines() 
    words = [ ''.join([ c for c in x.lower() \ 
       if ord('a') <= ord(c) <= ord('z') ]) \ 
      for x in words ] 
    for x in words: 
     try: 
      make_key(x) 
     except: 
      print x 
      raise 

except IOError: 
    words = [ 'reawaken','awaken','enwrap','weaken','weaker', ] 

words = dict(((make_key(x),x,) for x in words)) 


inputs = sys.argv[1:] if sys.argv[1:] else [ 'raepkwaen', ] 
for input in inputs: 
    input_key = make_key(input) 
    results = [ words[x] for x in words if input_key % x == 0 ] 

    result = reversed(sorted(results, key=len)).next() 
    print input,'--> ',result 

Answer 7

DAWG (निर्देशित अचक्रीय वर्ड ग्राफ) मार्क Wutka तरह पर्याप्त यहाँ कुछ पास्कल कोड प्रदान करना था।

• http://www.wutka.com/dawg.html
• http://www.wutka.com/DictConvert.ZIP

Answer 8

मैं इस कल रात शुरू कर दिया कुछ ही समय बाद आप प्रश्न पूछा है, लेकिन यह चमकाने अप अभी तक करने के लिए चारों ओर नहीं मिला। यह मेरा समाधान था, जो मूल रूप से एक संशोधित त्रिभुज है, जिसे मैं आज तक नहीं जानता था!

class Node(object): 
    __slots__ = ('words', 'letter', 'child', 'sib') 

    def __init__(self, letter, sib=None): 
     self.words = [] 
     self.letter = letter 
     self.child = None 
     self.sib = sib 

    def get_child(self, letter, create=False): 
     child = self.child 
     if not child or child.letter > letter: 
      if create: 
       self.child = Node(letter, child) 
       return self.child 
      return None 
     return child.get_sibling(letter, create) 

    def get_sibling(self, letter, create=False): 
     node = self 
     while node: 
      if node.letter == letter: 
       return node 
      sib = node.sib 
      if not sib or sib.letter > letter: 
       if create: 
        node.sib = Node(letter, sib) 
        node = node.sib 
        return node 
       return None 
      node = sib 
     return None 

    def __repr__(self): 
     return '<Node({}){}{}: {}>'.format(chr(self.letter), 'C' if self.child else '', 'S' if self.sib else '', self.words) 

def add_word(root, word): 
    word = word.lower().strip() 
    letters = [ord(c) for c in sorted(word)] 
    node = root 
    for letter in letters: 
     node = node.get_child(letter, True) 
    node.words.append(word) 

def find_max_word(root, word): 
    word = word.lower().strip() 
    letters = [ord(c) for c in sorted(word)] 
    words = [] 
    def grab_words(root, letters): 
     last = None 
     for idx, letter in enumerate(letters): 
      if letter == last: # prevents duplication 
       continue 
      node = root.get_child(letter) 
      if node: 
       words.extend(node.words) 
       grab_words(node, letters[idx+1:]) 
      last = letter 
    grab_words(root, letters) 
    return words 

root = Node(0) 
with open('/path/to/dict/file', 'rt') as f: 
    for word in f: 
     add_word(root, word) 

परीक्षण:

>>> def nonrepeating_words(): 
...  return find_max_word(root, 'abcdefghijklmnopqrstuvwxyz') 
... 
>>> sorted(nonrepeating_words(), key=len)[-10:] 
['ambidextrously', 'troublemakings', 'dermatoglyphic', 'hydromagnetics', 'hydropneumatic', 'pyruvaldoxines', 'hyperabductions', 'uncopyrightable', 'dermatoglyphics', 'endolymphaticus'] 
>>> len(nonrepeating_words()) 
67590 

मुझे लगता है मैं सबसे लंबा शब्द के लिए uncopyrightable को dermatoglyphics पसंद करते हैं, अपने आप को लगता है। अभिनय की दृष्टि से, एक ~ 500k शब्द शब्दकोश (here से) का उपयोग,

>>> import timeit 
>>> timeit.timeit(nonrepeating_words, number=100) 
62.8912091255188 
>>> 

तो, औसतन, एक दूसरे (मेरी i5-2500 पर) 6/10ths सभी के सभी साठ-सात हजार शब्दों जिनकी करने के लिए कोई दोहराव पत्र नहीं।

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

ओह, और बस के लिए गिगल्स:

>>> sorted(tree.find_max_word('RAEPKWAEN'), key=len)[-5:] 
['wakener', 'rewaken', 'reawake', 'reawaken', 'awakener'] 

Answer 9

एक और दृष्टिकोण, @ बाजार के जवाब के लिए इसी तरह, एक शब्दकोश में प्रत्येक शब्द के लिए 'bitmask' precompute है। बिट 0 सेट किया गया है यदि शब्द में कम से कम एक ए है, तो बिट 1 सेट किया गया है यदि इसमें कम से कम एक बी है, और इसलिए Z.

के लिए बिट 25 तक सेट करें यदि आप शब्दकोश में सभी शब्दों को खोजना चाहते हैं जिसे अक्षरों के संयोजन से बनाया जा सकता है, आप अक्षरों के संग्रह के लिए बिटमैस्क बनाकर शुरू करते हैं। फिर आप wordBitmask & ~lettersBitMask शून्य है या नहीं, यह जांच कर अन्य शब्दों का उपयोग करने वाले सभी शब्दों को फ़िल्टर कर सकते हैं। यदि यह शून्य है, तो शब्द केवल संग्रह में उपलब्ध अक्षरों का उपयोग करता है, और इसलिए मान्य हो सकता है। यदि यह शून्य है, तो यह संग्रह में उपलब्ध एक पत्र का उपयोग नहीं करता है और इसलिए इसकी अनुमति नहीं है।

इस दृष्टिकोण का लाभ यह है कि बिटवाई ऑपरेशंस तेज़ हैं। शब्दकोश में अधिकांश शब्द 17 या उससे अधिक अक्षरों में से एक का उपयोग करेंगे जो संग्रह में नहीं हैं, और आप उन्हें आसानी से छूट सकते हैं। हालांकि, फ़िल्टर के माध्यम से इसे बनाने वाले शब्दों की अल्पसंख्यकता के लिए, एक और जांच है जिसे आपको अभी भी करना है। आपको अभी भी यह जांचना होगा कि शब्द संग्रह में दिखाई देने से अधिक बार अक्षरों का उपयोग नहीं कर रहे हैं। उदाहरण के लिए, 'कमजोर' शब्द को अस्वीकार कर दिया जाना चाहिए क्योंकि इसमें तीन 'ई है, जबकि अक्षरों के संग्रह में केवल दो ही हैं। अकेले bitwise दृष्टिकोण इस शब्द को फ़िल्टर नहीं करेगा क्योंकि शब्द में प्रत्येक अक्षर संग्रह में प्रकट होता है।