アナグラムグルーピング

「仲間かどうか」を総当たりで確かめない

eat, tea, tan, ate, nat, bat を、文字を並べ替えると一致するもの同士でまとめます。eat と tea と ate が 1 組、tan と nat が 1 組、bat は 1 語だけの組です。こういう関係をアナグラムと言います。

素直にやるなら、すべての 2 語の組について「並べ替えたら一致するか」を確かめます。語数の 2 乗に比例するので、1 万語なら 5,000 万回。そのうえ、A と B が仲間で B と C も仲間だと分かったあとに A と C を確かめるのは、完全に無駄な作業です。

比べるのをやめます。代わりに、仲間なら必ず同じになる合言葉を語ごとに 1 回だけ作り、同じ合言葉の語を同じ箱に入れます。

合言葉で箱に配る

配る形そのものは、どんな合言葉でも変わりません。ここでは文字数を合言葉にしてみます。

文字数で分類する例:
fig (3) → 3 文字の箱を作る → [fig]
kiwi (4) → 4 文字の箱を作る → [kiwi]
pear (4) → 既存の 4 文字の箱へ → [kiwi, pear]
ant (3) → 既存の 3 文字の箱へ → [fig, ant]

語を 1 回ずつしか見ていません。箱が無ければ作り、あればそこへ足すだけです。あとは合言葉の作り方を差し替えれば、好きな基準でまとめられます。

手間が語数に比例するのは、辞書が「この合言葉の箱はどこか」をほぼ一瞬で答えるからです。箱を順に見て回って探すなら、結局は総当たりに戻ってしまいます。1 万語なら、5,000 万回が 1 万回になります。

合言葉に、文字の個数が残っているか

アナグラムの合言葉に求められる条件は 2 つです。同じ文字を同じ個数だけ持つ 2 語が必ず同じ値になることと、構成が違う 2 語が必ず違う値になること。

たとえば「使われている文字の集まり」を合言葉にすると、後者で失敗します。aab も ab も集まりにすれば a と b なので、同じ箱に入ってしまいます。個数の情報が消えているからです。文字の並び順に左右されず、しかも個数まで残る形を探してください。

出てきた順を保つ

箱の並びは、その合言葉が最初に登場した順にします。Python の辞書と JavaScript の Map は入れた順を覚えているので、そのままで条件を満たします。Java の HashMap は順を保証しないので LinkedHashMap を使い、Go の map も順を保証しないので、合言葉の登場順を別のスライスに記録しておく必要があります。箱の中身のほうは、語を見つけた順に足していけば自然に入力順のままです。

演習で使う書き方

例として "cab" を sorted で並べると ["a", "b", "c"] になり、"".join(...) で "abc" へつながります。辞書は {} で作り、in でキーの有無を調べ、添字で箱を登録・取得します。例えば boxes["果物"] = [] は空の箱の登録です。キーの作成と箱の用意・追加を自分で書きます。出力の配列化だけは補助関数にしました。

1. 文字の並びをそろえたキーと箱への分類を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える