在指定时间内查找排列的所有匹配

我正在编写一个需要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

在指定时间内查找排列的所有匹配

回答

相关问题