2

私の入力が次のようなリストの場合:

words = ['cat','act','wer','erw']

このようなアナグラムのリストのリストを作成したい -

[['cat','act'],['wer','erw']]

私はこのようなことをしようとしました:

[[w1 for w in words if w!=w1 and sorted(w1)==sorted(w)] for w1 in words]

しかし、うまくいきません。出力は次のとおりです。

[['cat'], ['act'], ['wer'], ['erw']]

さらに、インポートを使用したくありません (文字列を除く)。間違いは何ですか？

4

4 に答える 4

3

元の方法は実際には O(#words 2 ) 時間であるため、おそらく 10000 語を超える大規模なデータセットでは機能しないことに注意してください。

groupby ワンライナー:

私が今まで見た中で最もエレガントitertools.groupbyで奇妙な使用例の 1 つ:

>>> [list(v) for k,v in groupby(sorted(words,key=sorted),sorted)]
[['cat', 'act'], ['wer', 'erw']]

defaultdict 3ライナー:

を使用するcollections.defaultdictと、次のことができます。

anagrams = defaultdict(list)
for w in words:
    anagrams[tuple(sorted(w))].append(w)

インポートなしで元の方法で行う場合はcollections.defaultdict、次のようにエミュレートできます。

anagrams = {}
for w in words:
    key = tuple(sorted(w))
    anagrams.setdefault(key,[]).append(w)

例：

>>> anagrams
{('e', 'r', 'w'): ['wer', 'erw'], ('a', 'c', 't'): ['cat', 'act']}

（ whiの回答にも書かれています。）

マップ縮小:

この問題は、使用するリダクション キーがソートされた文字 (より効率的にはハッシュ) である map-reduce の代表的な問題でもあります。これにより、問題を大規模に並列化できます。

単語の長さが制限されていると仮定すると、groupby解はO(#words log(#words))であり、ハッシュ解は と予想されO(#words)ます。万一、単語の長さが任意の長さである場合、並べ替え (O(length log(length))単語ごと) は、順序にとらわれない文字のハッシュ (単語ごと) を使用するよりも効率的ではありませんO(length)。残念ながら、 collections.Counter はハッシュ可能ではないため、独自に作成する必要があります。

于 2012-06-02T08:20:10.423 に答える
2 
words = ['cat','act','wer','erw']
dic={}
for w in words:
    k=''.join(sorted(w))
    dic.setdefault(k,[])
    dic[k].append(w)
print dic.values()

これはパフォーマンスが優れています: O(n)

于 2012-06-02T08:27:06.300 に答える
0

ググると、一度に 1 つの単語のアナグラムのさまざまな解決策を見つけることができます。明らかな「知っているすべての単語を検索して、同じ文字があるかどうかを確認する」よりも効率的なソルバーが存在する可能性があります。

1 つ取得したら、それを関数に入れることができます。

def anagrams(word):
    "return a list of all known anagrams of *word*"

それができたら、それを単語のリストに一般化するのは簡単です。

[anagrams(word) for word in words]
于 2012-06-02T08:12:06.607 に答える
0

これは、好みのスタイルでトリックを行う必要があります

[[w, w1] for w1 in words for w in words if w!=w1 and sorted(w1)==sorted(w)][::2]
于 2012-06-02T08:38:58.353 に答える