質問
これをスクラブルスタイルの問題として分類できると思いますが、友人が英国のテレビクイズショーカウントダウンに言及しているために始まりました。ショーのさまざまなラウンドでは、競技者がスクランブルされた一連の文字を提示されていることを伴い、彼らはできる限り長い言葉を考え出さなければなりません。私の友人が言及したのは「Raepkwaen」でした。
かなり短い順序で、私はこの問題を処理するためにこの問題を処理するためにPythonで何かをホイップしました。
これが私が現在持っているものです:
#!/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文字の例では問題ありません。その規模では、可能なすべての順列と単語の長さをチェックする必要がある場合でも、それほど多くはありません。
ただし、14文字に達すると、87,178,291,200の可能性のある組み合わせがあります。つまり、14文字の単語がすぐに見つかることを運んでいます。
上記の単語の例を使用すると、私のマシンを約12 1/2秒で撮影して「再覚醒」を見つけます。 14文字のスクランブルワードでは、可能なすべての14文字の順列をチェックするために、23日間のスケールで話すことができます。
これを処理するためのこれ以上の効率的な方法はありますか?
正しい解決策はありません
所属していません StackOverflow