お題

タイトルの通り
英語の辞書が与えられたときにすべてのアナグラムを見つける

アナグラムは同じ文字を異なる順番で使った単語のこと
例えば、[from, form], [time, item]など

単純なやり方としては
単語を1文字ずつずらして、すべての単語についてマッチするか見ていく

しかし、英単語の総数は100万以上らしく、5文字の単語を検査するのにも

5! * 10^{6} = 1.2 * 10^{8}

1回ごとの比較処理が1μ秒だとしても

10^{8}/回 * 10^{-6}秒/回 = 100秒

かかってしまう

上記例は英単語の総数として出していますが、よく調べたら英辞典は17万ほどの収録だそうです

じゃあ、どうすればいいかが本題

答えとしては同じアナグラムのグループに印をつけるということ
そして、同じ印のついた単語をまとめておけば目的が達成されます。

印のつけかたは、各単語の文字列をアルファベット順に並べ替える
単純ですが効果的ですよね、なるほど。。

そうとわかれば後はデータの持ち方きめればすぐに実装できそうですね
こんな感じでやってみました

playground

package plg

import (
	"fmt"
	"sort"
	"strings"
)

var (
	dummyDict = []string{"from", "time", "item", "form", "off", "test"}
)

func Anagram() {
	// 容量割り当てときたいが目安がわからないので保留
	list := make(map[string][]string)

	for _, word := range dummyDict {
		key := sortStr(word)
		list[key] = append(list[key], word)
	}

	for _, words := range list {
		for _, w := range words {
			fmt.Print(w, " ")
		}
		fmt.Println()
	}
}

func sortStr(k string) string {
	s := strings.Split(k, "")
	sort.Strings(s)

	return strings.Join(s, "")
}

output

from form 
time item 
off 
test

うん、うまくいってますね

一意のグループを表すキーを作るためにソートを使うっていうのは
知ってないと思いつかないので勉強になりました。