アナグラム
意外な単語がアナグラムだったりします。
thread
HATRED
reproduce
PROCEDURE
thousand
HANDOUTS
generate
TEENAGER
process
CORPSES
PROCESS
ruby -e'class String; def sort(); self.split(//).sort.join;end;end; dic={}; ARGV.each{|f| File.open(f).each{|x| x.chomp!; y=x.upcase.gsub(/\W/,""); sy = y.sort; dic[sy] ||= {}; dic[sy][y]=1;}}; STDIN.each{|x| puts((dic[x.upcase.gsub(/\W/,"").sort] || {""=>1}).keys)}' /usr/share/dict/{american,british}-english <(ruby -e'STDIN.each{|x| y=Regexp.new("
(.*?) (.*?) ").match(x); if y then; puts y[2]; end}'< /usr/share/dict/jedict.sdic | kakasi -Ha |kakasi -Ka| iconv -f euc-jp -t utf-8)
引数にファイルを取る。
ファイルの形式は一行一単語。
単語はユーザーが入力する文字列と同じ文字セットと仮定する。
単語をソートしたときのハッシュ値を使って単語の同値類を作る。
2番目のシングルクォート以降にかかれている引数ファイルを、
ユーザーの環境に合わせて調整する。
あとでやる：
活用展開済みの形態素解析辞書を使って、
その辞書での最大アナグラムを見つける。
あとできづいた：
Programming Pearls で既出
sign | sort | squash
http://www.cs.bell-labs.com/cm/cs/pearls/s02.pdf
(2007-12-25T11:35:00+0900)
翻訳アナグラム問題 TransAnagram(A,B)
2つの文字列集合A,Bが与えられる。
a \in A, b \in B かつ、a は bのアナグラムであるような対
(a,b)をすべて出力せよ。
（あるいは、アナグラム同値類のうち、A,Bの両方にまたがるものを列挙せよ）
guitar
GUITAR
TAGURI
TAGIRU
chaos
CHAOS
SOCHA
pain
ANPI
tuesday
TUESDAY
YATSUDE
YATSUDE
heuristic
ICHIRETSU
HEURISTIC
hatena
ATHENA
(2007-12-25T11:37:57+0900)
Anagram(A) = TransAnagram(A,A)
(2007-12-25T11:39:20+0900)
TransAnagramの解１
A,Bを混ぜてAnagramを解く。
その出力のうち、A,Bの要素が混在している同値類が出力である。
(2007-12-25T11:45:10+0900)
練習問題
AnagramはP問題か？
(2007-12-25T15:16:56+0900)
See also:
http://www.notwork.org/~gotoken/mag/cmagazine/gokudo/8th/
文字を素数に置き換えて、ハッシュ値の計算を高速化する
http://blog.notdot.net/archives/38-Damn-Cool-Algorithms,-Part-3-Anagram-Trees.html
半順序関係である is-a-subanagram-of に関する列挙のための Anagram Trees
