3

これのバリエーションが以前に尋ねられたことは知っていますが、以前の実装のほとんどがセットと issubset メソッドを使用していたため、以前の実装を理解できませんでした。

これが私がやろうとしていることです: 私は辞書に単語のセットと可能な文字のリストを持っています. リスト内の文字を並べ替えることで、セットのメンバーを形成できるかどうかを調べたい. これが私の現在の実装です：

def solve(dictionary, letters):

    for word in dictionary: #for each word in the dictionary
        if len(word) > len(letters):   # first optimization, doesn't check words that are larger than letter set
            continue
        else: 
            scrambledword = "".join([b for b in sorted(list(word))]) #sorts the letters in each word
            if set(scrambledword).issubset(letters):
                print word


def main():
    dictionary = set([x.strip() for x in open("C:\\Python27\\dictionary.txt")])        
    letters = sorted(['v','r','o','o','m','a','b','c','d'])
    solve(dictionary, letters)


main()

この実装の明らかな問題は、「文字」に複数の文字を使用する単語が見つかることです。たとえば、文字リストに「a」と「r」のコピーが 1 つしかないにもかかわらず、「cardboard」という単語は有効な単語として表示されます。リストで「issubset」メソッドを使用するにはどうすればよいですか?

4

3 に答える 3

5

一連の文字から単語を作成できるかどうかを知るには [おっと、私は自分でやった - 「コレクション」を意味していた!]、すべての文字が少なくとも適切な回数出現することを望むので、私は思う.どういうわけかそこでカウントを処理する必要があります。定義上、Python セットはソース リスト内の要素の数を気にしません。多分何かのような

from collections import Counter

letters = ['v','r','o','o','m','a','b','c','d']
words = 'cardboard boom booom'.split()
letterscount = Counter(letters)

for word in words:
    wordcount = Counter(word)
    print word, all(letterscount[c] >= wordcount[c] for c in wordcount)

与える

cardboard False
boom True
booom False

Counter は便利なユーティリティ クラスです。

>>> c = Counter(letters)
>>> c
Counter({'o': 2, 'a': 1, 'c': 1, 'b': 1, 'd': 1, 'm': 1, 'r': 1, 'v': 1})
>>> c['o']
2
>>> c['z']
0

【DSM】お返し！Counter インスタンスがハッシュ可能でないために機能しないコミュニティ編集を削除しました。]

検索速度が問題になる場合は、メモリと事前計算時間をトレードオフできます。

from collections import defaultdict, Counter
from itertools import combinations

# precomputations
allwords = open('/usr/share/dict/words').read().split() 
allwords = list(w for w in allwords if len(w) >= 3) # hack, /words contains lots of silliness
allwords_by_count = defaultdict(list)
for i, word in enumerate(allwords):
    allwords_by_count[frozenset(word)].append((word, Counter(word)))
    if i % 1000 == 0:
        print i, word


def wordsfrom(letters, words_by_count):
    lettercount = Counter(letters)
    for subsetsize in range(1, len(lettercount)+1):
        for subset in combinations(lettercount, subsetsize):
            for possword, posswordcount in words_by_count[frozenset(subset)]:
                if all(posswordcount[c] <= lettercount[c] for c in posswordcount):
                    yield possword

>>> wordsfrom('thistles', allwords_by_count)
<generator object wordsfrom at 0x1032956e0>
>>> list(wordsfrom('thistles', allwords_by_count))
['ess', 'sis', 'tit', 'tst', 'hei', 'hie', 'lei', 'lie', 'sie', 'sise', 'tie', 'tite', 'she', 'het', 'teth', 'the', 'els', 'less', 'elt', 'let', 'telt', 'set', 'sett', 'stet', 'test', 'his', 'hiss', 'shi', 'sish', 'hit', 'lis', 'liss', 'sil', 'lit', 'til', 'tilt', 'ist', 'its', 'sist', 'sit', 'shies', 'tithe', 'isle', 'sile', 'sisel', 'lite', 'teil', 'teli', 'tile', 'title', 'seit', 'sesti', 'site', 'stite', 'testis', 'hest', 'seth', 'lest', 'selt', 'lish', 'slish', 'hilt', 'lith', 'tilth', 'hist', 'sith', 'stith', 'this', 'list', 'silt', 'slit', 'stilt', 'liesh', 'shiel', 'lithe', 'shiest', 'sithe', 'theist', 'thesis', 'islet', 'istle', 'sistle', 'slite', 'stile', 'stilet', 'hitless', 'tehsil', 'thistle']

[へぇ。「アザミ」自体がリストにないことに気付きましたが、それは単語ファイルにないためです..]

はい、明らかな「非単語」は実際には単語ファイルにあります。

>>> assert all(w in allwords for w in (wordsfrom('thistles', allwords_by_count)))
>>>
于 2011-06-13T04:32:07.400 に答える
1

アナグラムを探している場合、つまり、再配置したいが、(サブセットのみを使用するのではなく) すべてを使用する場合は、別の解決策があります。

まず、辞書内のすべての単語を前処理します。単語を指定すると、同じ文字でアルファベット順に書かれた単語が生成されます。

def alphabetize(word):
    "".join(sorted(word))

これらの新しい単語をセットに入れnewDictionary ます次に、関数は文字のアルファベット順を呼び出し、結果が辞書にあるかどうかを確認できます。

def solve(newDictionary, letters):
    query = alphabetize(letters)
    return query in newDictionary

アルファベット化機能はアナグラムの特徴です。アルファベット化を適用したときに同じ結果が得られる場合にのみ、2 つの単語が互いのアナグラムになります。

于 2011-06-13T05:16:40.513 に答える
0

をインポートcollectionsして、ハッシュ可能なマルチセットを定義します。

def Letters(x):
    return frozenset(Counter(x).items())

ここで、語彙を文字の辞書に前処理します->{anagram1,anagram2,...}:

vocabulary = ['apple', 'banana', 'rats', 'star', 'tars']
countsToWords = defaultdict(lambda: set())
for word in vocabulary:
    countsToWords[Letters(word)].add(word)

あなたの「解決」関数は O(1) 時間かかります:

def solve(query):
    return countsToWords[Letters(query)]

例：

print( solve('star') )
# {'tars', 'star', 'rats'}
于 2011-06-13T05:09:32.980 に答える