アルゴリズムの勉強１

大学の講義でかなり本格的なプログラミングとアルゴリズムの話題が出始めたので楽しくなってきました。そこで関連書として、前から読もう読もうと思っていた本を借りてきました。

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

とても難しいです。返却日までにおそらく半分も理解しきれないと思います。

この本の最初の方に、アルゴリズムを考える例として、与えられた文字列リストの中からanagramの組を列挙するというものがありました。

anagramとは、

のことです。（Wikipediaより）

問題を読んだときにパッと思い浮かんだ解法が、たまたま、ほぼ正解な方法だったようで嬉しかったです。私が思いついた手順のアイデアとしては、

1. 単語自身を辞書順にソートする。これをキーとして、単語と一緒に保持しておく。
2. 複数の「キーと単語のセットの文字列」をソートする。
3. 同じキーを持っている単語同士をanagramとして判別し、表示する。

という感じです。例として単語のセットを cat, pot, act, top, egg, opt として、上記の手順にそって判定してみまると、

1. キー 単語 のように保持するので、act cat, opt pot, act act, opt top, egg egg, opt opt となる。
2. 文字列をソートすると、act act, act cat, egg egg, opt opt, opt pot, opt top となる。
3. ここまでの操作により、actをキーとするグループとoptをキーとするグループのanagramの組み合わせを見つけることができる。

まだ始めたばかりですが、しっかりと開放の手順を考える作業は楽しいと思っています。

また、「よし、これくらいならコードも書けるだろう」と思って、いざPythonを書いてみると案外いろいろなところ（文法構文において）で躓き時間がかかりました。実際に手を使って書いてみることは重要だと再認識しました。

気長に頑張ろうと思います。

おまけ

私が書いたコードへのリンクです。サンプルの単語セットは一部本のものをお借りしましたが、コードは掲載されているものではありません。本ではもっと美しいコードが紹介されています！