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

Question

我正在编写一个程序，该程序需要 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这是我正在从中抓取字典文件的网站。

Answer 1

在测试它们是否有效之前，将所有排列存储在列表中会浪费 RAM 和时间。相反，在生成排列时对其进行测试，并将有效的排列保存到一组中以消除重复。

由于 itertools.permutations 的方式，重复是可能的作品:

Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each permutation.

您的输入单词“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

这段代码在我的相当古老的 32 位 2GHz 机器上运行大约 2.5 秒，在 Linux 上运行 Python 3.6.0。在 Python 2 上速度稍快一些(因为 Python2 字符串是 ASCII，而不是 Unicode)。