💡

アナグラム探索

2024/03/11に公開

しばらく前にアナグラム探索をするプログラムを Rust で書いた。

https://github.com/SaitoAtsushi/anagram

素数の性質を利用すれば簡単というのをどこかで見たことがあったので実際にやってみると想像以上に短いコードで書けて驚いた。

素数を利用するというのは、文字に素数を対応付けるという方法だ。 文字列に含まれる文字を素数に対応づけて掛け算したものは文字列内の文字の順番をどう入れ替えても同じなのでアナグラムの判定に使える。

そしてアナグラムの判定に使えるというだけでなく、アナグラムの一部を構成する文字列として使えるかどうかは割り切れるかどうかを確かめてみればいいので複数の語を組み合わせてアナグラムを作ろうとするときに便利という性質もある。

Discussion