今日の風景

f:id:nisemono_san:20161004044324j:plain

はじめに

元々は永和システムマネジメントの技術面接で出された問題らしい。こく難しく言えば「ある文字列」(この文字列の集合をAとすると)と「ある文字列」(この文字列の集合をBとする)とした場合、このAとBの文字列の集合が一緒であるかどうかをどのように判定するか、という問題らしい。もうすこし簡単に言えば、Bの文字列はAの文字列かどうかをどのように判定するかということである。

この問題の解き方は簡単で、先に言ってしまえば次のようになる:

def anagram(s1, s2)
  s1.chars.sort == s2.chars.sort
end

これは、順序を考慮しない集合の場合、同じ要素が一対一になっていればいいということなわけだから、とてもシンプルでわかりやすい解答である。ただ、元のエントリが「Scheme」で書かれているので、Redditの日本語Lispコミュニティにも言及された(r/lisp_jaで見つけることができる)。その中のコメントで、とても秀逸なコメントをみつけたので紹介したい。

もし ASCII コードの範囲内だけとかいった、文字数が限定的であるような条件が付いていた場合には文字コードを素数に対応つけて掛け算するという方法がありますね。文字の並び順にかかわらず同じ文字を同じ回数使っていれば同じ値になります。 Unicode 全体とかいった巨大な文字セットだと単純にソートした方が速いと思いますが……。

どういうことかというと、スレッドにも書いてあるとおり、「素因数で生成された積」は一緒にならない。このような理論は、例えば暗号技術に使われているし、またゲーデルの不完全性定理でも、このようにある文字列を素数の積として表現し、メタ的に判定に使われることがある。

このアルゴリズムは面白いので、さっそく自前で実装してみることにした。(本当はLispでの話題なのでLispのほうがいいかもしれませんが、Rubyでやります)

実装

require 'prime'

class String
  def to_prime_s
    t = prime_table
    return self.split('').map { |c| t[c] }.inject(:+)
  end

  private
  def prime_table
    alpha = ([*'a'..'z'] + [*'A'..'Z'] + [" "])
    Hash[alpha.zip(Prime.each.take(alpha.size).to_a)]
  end
end

def prime_calc(origin, anag)
  puts origin
  puts anag
  origin.to_prime_s == anag.to_prime_s
end

def string_shuffle(s)
  s.split('').shuffle.join('')
end


p prime_calc('Esehara Shigeo', string_shuffle('Eseraha Shigeo'))
p prime_calc('Esehara Shigeo', string_shuffle('Eseraha Shideo'))

特に特殊なことはしていない。あるとするならば、アルファベットと素数のHashを作っているくらいだろう。ただ、これだけだと、メソッドが呼びだされるたびにHashが作られるので、本来であるならばキャッシュするのがいいだろう。今回は二回のみだけなので、このような実装をしている。実行してみると、下のようになる:

Esehara Shigeo
hrSeieah goasE
true

Esehara Shigeo
ioahEseSa ehrd
false

雑感

このアルゴリズムの問題点は元のスレッドでも議論されているように、まず文字種が多い場合、それに対応した素数を増やさなければならないので、例えばUnicode全体を網羅しようとすると地獄になる。

また、長い文章に対応させるとなると、その分だけ素数の積を計算しなければいけなくなるので、計算量も膨大になるというデメリットがある。ただ、そのかわり複数の単語からなる文章のアナグラムも探しやすくなるということのようだ。

まとめ

というわけで、今回はネットから拾ってきたものをネタにしてみた。自分も、「なんかソートして、その文字列を比較するのはずるいなー、なんか方法ないかしら」と考えていたものだから、今回の方法は目から鱗だった。こういう風に何気ない一言で開眼できるのが、インターネットのいいところだと思う。

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

アナグラムを素数の積で求めると簡単(ではないけど)判定できるよって話

今日の風景

はじめに

実装

雑感

まとめ