アナグラム

アナグラム (anagram) とは言葉遊びの一つで、単語または文の中の文字をいくつか入れ替えることによって全く別の意味にさせる遊びである。(Wikipediaより)

このとき、ひらがな/カタカナのアナグラムは見てすぐに分かるが、ローマ字のアナグラムは見てわかるものではない。

というわけで、ローマ字のアナグラムを生成するプログラムをRubyで組んでみた。


#!/usr/bin/ruby

$roman_jletter = /^(\s|[n]|[t][s][u]?|([kstcnhmrgzjdbp]?[y]?|[stcwd]?[h]?|[fw]?)[aiueo])*$/
$roman_jletter_process = /^(\s|[n]|[t][s][u]?|([kstcnhmrgzjdbp]?[y]?|[stcwd]?[h]?|[fw]?)[aiueo])*([t][s]|[kstcnhmrgzjdbp]?[y]?|[stcwd]?[h]?|[fw])?$/

class String
 def print_ano_name(tmp = '')
  if self == '' then
   if tmp =~ $roman_jletter then
    p tmp
   end
  elsif tmp =~ $roman_jletter_process then
   i=0
   self.each_byte{|k|
    if self.index(k.chr) == i
     (self[0...i] + self[(i+1)..self.length]).print_ano_name(tmp+k.chr)
    end
    i=i+1
   }
  end
 end
end

ARGV[0].to_s.print_ano_name

注意としては、扱う文字が長くなると、計算時間が一気に長くなること。
上記プログラムに、文字列「takumi kanno」を与えたところ、95分かかっている。
プログラム内で少しは枝を切っている(=途中で計算を打ちきることで、余分な計算をしないようにしている)が、文字列が長くなると、枝切りでも間に合わなくなる。

正規表現の与え方を工夫すれば計算速度は早くなりそうだが、計算量のオーダーに効いてこなさそうなのであんまし興味なし。

タグ: , ,

コメントをどうぞ