在指定時間內查找排列的所有匹配

我正在編寫一個需要9個字符的程序，創建所有可能的排列，併爲每個字符抓取字典文件，然後創建一組所有可能的單詞。我需要做的是將所有排列與單詞進行比較並返回匹配。在指定時間內查找排列的所有匹配

import os, itertools 

def parsed(choices): 
    mySet = set() 
    location = os.getcwd() 
    for item in choices: 
     filename = location + "\\dicts\\%s.txt" % (item) 
     mySet.update(open(filename).read().splitlines()) 

    return mySet 

def permutations(input): 
    possibilities = [] 
    pospos = [] 

    for x in range(3,9): 
     pospos.append([''.join(i) for i in itertools.permutations(input, x)]) 


    for pos in pospos: 
     for i in pos: 
      possibilities.append(i) 
    return possibilities

有問題的功能是這一個：

def return_matches(): 
    matches = [] 
    words = parsed(['s','m','o','k','e', 'j', 'a', 'c', 'k']) 
    pos = permutations(['s','m','o','k','e', 'j', 'a', 'c', 'k']) 

    for item in pos: 
     if item in words: 
      matches.append(item) 

    return matches

此代碼應返回：

matches = ['a', 'om', 'ja', 'jo', ..., 'jacks', 'cokes', 'kecks', 'jokes', 'cakes', 'smoke', 'comes', 'makes', 'cameos']

如果我得到這個代碼能夠正常工作，它需要10 - 15分鐘才能完成。另一方面，每次嘗試在指定的時間內執行該操作，只能使用5個或更少的字符或返回錯誤的結果。

所以我的問題是如何優化此代碼返回正確的結果，在30秒的時間內。

編輯 http://www.mso.anu.edu.au/~ralph/OPTED/v003這是我抓取字典文件的網站。

來源

2017-02-13 Notgivinit

你是什麼意思「我有這個代碼，因爲它應該工作，但是......它要麼需要10-15分鐘，或不返回正確的結果「？如果它按原樣工作，它怎麼能不能返回正確的結果？ –

我的意思是返回正確的結果，但它需要很長的時間（10 - 15分鐘），或者它不起作用。我會編輯這一點。我爲我的措辭道歉。 – Notgivinit

我假設您已經使用www.mso.anu.edu.au中的這些文件構建自己的單詞列表文件，剝離定義並在每行放置一個單詞。我建議使用我在前一個問題的評論中鏈接的SOWPODS文件。然而，它是一個拼字遊戲單詞列表，所以它不包含一個字母單詞，所以你需要用這些單詞初始化你的單詞集，例如'set（'AI'）。 –

在測試它們是否有效之前，它浪費RAM和時間將所有排列存儲在列表中。相反，在生成它們時測試排列，並將有效的排列保存到一個集合中以消除重複。

因爲重複的方式itertools.permutations作品是可能的：

元素被作爲唯一的治療基於自己的立場，而不是他們的價值。因此，如果輸入元素是唯一的，那麼在每個排列中將不會有重複的值。

您輸入的單詞「SMOKEJACK」包含2個K，因此每個包含K的排列都會生成兩次。

無論如何，這裏有一些代碼使用SOWPODS英文拼字單詞列表。

from itertools import permutations 

# Get all the words from the SOWPODS file 
all_words = set('AI') 
fname = 'scrabble_wordlist_sowpods.txt' 
with open(fname) as f: 
    all_words.update(f.read().splitlines()) 

print(len(all_words)) 

choices = 'SMOKEJACK' 

# Generate all permutations of `choices` from length 3 to 8 
# and save them in a set to eliminate duplicates. 
matches = set() 
for n in range(3, 9): 
    for t in permutations(choices, n): 
     s = ''.join(t) 
     if s in all_words: 
      matches.add(s) 

for i, s in enumerate(sorted(matches)): 
    print('{:3} {}'.format(i, s))

輸出

216555 
    0 ACE 
    1 ACES 
    2 ACME 
    3 ACMES 
    4 AESC 
    5 AKE 
    6 AKES 
    7 AMOK 
    8 AMOKS 
    9 ASK 
10 CAKE 
11 CAKES 
12 CAM 
13 CAME 
14 CAMEO 
15 CAMEOS 
16 CAMES 
17 CAMS 
18 CASE 
19 CASK 
20 CEAS 
21 COKE 
22 COKES 
23 COMA 
24 COMAE 
25 COMAKE 
26 COMAKES 
27 COMAS 
28 COME 
29 COMES 
30 COMS 
31 COS 
32 COSE 
33 COSMEA 
34 EAS 
35 EKKA 
36 EKKAS 
37 EMS 
38 JACK 
39 JACKS 
40 JAK 
41 JAKE 
42 JAKES 
43 JAKS 
44 JAM 
45 JAMES 
46 JAMS 
47 JOCK 
48 JOCKS 
49 JOE 
50 JOES 
51 JOKE 
52 JOKES 
53 KAE 
54 KAES 
55 KAM 
56 KAME 
57 KAMES 
58 KAS 
59 KEA 
60 KEAS 
61 KECK 
62 KECKS 
63 KEKS 
64 KOA 
65 KOAS 
66 KOS 
67 MAC 
68 MACE 
69 MACES 
70 MACK 
71 MACKS 
72 MACS 
73 MAE 
74 MAES 
75 MAK 
76 MAKE 
77 MAKES 
78 MAKO 
79 MAKOS 
80 MAKS 
81 MAS 
82 MASE 
83 MASK 
84 MES 
85 MESA 
86 MOA 
87 MOAS 
88 MOC 
89 MOCK 
90 MOCKS 
91 MOCS 
92 MOE 
93 MOES 
94 MOKE 
95 MOKES 
96 MOS 
97 MOSE 
98 MOSK 
99 OAK 
100 OAKS 
101 OCA 
102 OCAS 
103 OES 
104 OKA 
105 OKAS 
106 OKE 
107 OKES 
108 OMS 
109 OSE 
110 SAC 
111 SACK 
112 SAE 
113 SAKE 
114 SAM 
115 SAME 
116 SAMEK 
117 SCAM 
118 SEA 
119 SEAM 
120 SEC 
121 SECO 
122 SKA 
123 SKEO 
124 SMA 
125 SMACK 
126 SMOCK 
127 SMOKE 
128 SOAK 
129 SOC 
130 SOCA 
131 SOCK 
132 SOJA 
133 SOKE 
134 SOMA 
135 SOME

此代碼運行在大約2.5秒Linux上運行的Python 3.6.0我而古老的32位2GHz的機器上。它在Python 2上稍微快一點（因爲Python2字符串是ASCII，而不是Unicode）。

來源

2017-02-13 14:23:07

非常感謝你幫助我（在我的兩個問題中）。我真的很感謝你的幫助。 – Notgivinit

爲什麼你將排列限制爲3個或更多字母？是的，在OP的原始代碼中有類似的內容，但是再次，預期的輸出清楚地包含了一個和兩個字符的單詞。 –

@tobias_k在原始問題中，OP只需要全長排列。我使用OP代碼中顯示的'range（3，9）'而不是使用'range（1,1 + len（選項））'的主要原因是保持輸出的長度很小。 OP似乎很滿意我發佈的代碼... –

代替生成你的信的所有的排列，你應該使用Prefix Tree, or Trie，保留所有的前綴爲有效的話的軌道。

def make_trie(words): 
    res = {} 
    for word in words: 
     d = res 
     for c in word: 
      d = d.setdefault(c, {}) 
     d["."] = None 
    return res

我們正在使用d["."] = None這裏表示，其中一個前綴實際上成爲一個有效的字。創建樹可能需要幾秒鐘，但你只需要做一次。

現在，我們可以在遞歸函數中檢查我們的字母，檢查每個字母是否有助於遞歸的當前階段中的有效前綴：（那rest = letters[:i] + letters[i+1:]部分效率不高，但正如我們將看到的它並沒有多大關係）

def find_words(trie, letters, prefix=""): 
    if "." in trie: # found a full valid word 
     yield prefix 
    for i, c in enumerate(letters): 
     if c in trie: # contributes to valid prefix 
      rest = letters[:i] + letters[i+1:] 
      for res in find_words(trie[c], rest, prefix + c): 
       yield res # all words starting with that prefix

小例子：

>>> trie = make_trie(["cat", "cats", "act", "car", "carts", "cash"]) 
>>> trie 
{'a': {'c': {'t': {'.': None}}}, 'c': {'a': {'r': {'t': {'s': 
    {'.': None}}, '.': None}, 's': {'h': {'.': None}}, 't': 
    {'s': {'.': None}, '.': None}}}} 
>>> set(find_words(trie, "acst")) 
{'cat', 'act', 'cats'}

或與9個字母和單詞從sowpods.txt：

with open("sowpods.txt") as words: 
    trie = make_trie(map(str.strip, words)) # ~1.3 s on my system, only once 
    res = set(find_words(trie, "SMOKEJACK")) # ~2 ms on my system

您必須通過set來輸出結果，因爲您有重複的字母。在總共623次遞歸調用find_words（用計數器變量測量）之後，這將產生153個字。將其與sowpods.txt文件中的216,555個單詞相比較，並將所有1-9個字母組合中的986,409個排列組合成一個有效單詞。因此，一旦最初生成trie，res = set(find_words(...))僅需要幾毫秒。

你也可以改變find_words功能使用字母的可變字典計算而不是字符串或字母列表。這樣，不會生成重複項，並且該函數被調用次數更少，但總體運行時間並沒有太大變化。

def find_words(trie, letters, prefix=""): 
    if "." in trie: 
     yield prefix 
    for c in letters: 
     if letters[c] and c in trie: 
      letters[c] -= 1 
      for res in find_words(trie[c], letters, prefix + c): 
       yield res 
      letters[c] += 1

然後調用它像這樣：find_words(trie, collections.Counter("SMOKEJACK"))

來源

2017-02-13 20:23:54

謝謝你，雖然我的@PM 2Ring版本能夠完美工作，但我也絕對會用你的版本重寫代碼。不能學得太多。 – Notgivinit

在指定時間內查找排列的所有匹配

回答

相關問題