もうひとつ書いてみた

昨日の続き。
id:Cryolite:20050908:p3 のアルゴリズムも実装してみた。
こんな感じ：

require 'set'

L = {
#略
}

PLAYERS = L.keys

def each_combi( a0, n )
  return if a0.size<n || n<0
  if a0.size==n
    yield a0
  else
    a = a0.to_a
    tail = a[1..-1]
    each_combi( tail, n-1 ){ |x| yield( [a[0]]+x ) }
    each_combi( tail, n   ){ |x| yield( x ) }
  end
end

def log2( x )
  return x<=1 ? 0 : log2( x/2 )+1
end

subt = (0..log2( PLAYERS.size )).map{ Set.new }

each_combi(PLAYERS, 2 ){ |x,y|
  xwin=L[x][ y[0]-?A ]=='o'
  ywin=L[y][ x[0]-?A ]=='o'
  if xwin==ywin
    raise "which will win? : #{x},#{y}"
  elsif xwin
    subt[0] += [ [ x, y ] ]
  elsif ywin
    subt[0] += [ [ y, x ] ]
  else
    raise "unexpected."
  end
}

def cone( rule, a, b )
  def _cone( x, y )
    r = [x,y].flatten.uniq
    return r.size == x.size + y.size ? r : nil
  end
  if a[0]==rule[0] && b[0]==rule[1]
    _cone( a, b )
  elsif b[0]==rule[0] && a[0]==rule[1]
    _cone( b, a )
  else
    nil
  end
end

def progress( subt, n, target )
  each_combi( subt[ n-1 ], 2 ){ |x|
    subt[0].each{ |z|
      r = cone( z, x[0], x[1] )
      next if !r
      next if r[0]!=target && r.member?( target ) # 枝刈り
      subt[n] += [r]
    }
  }
end

log2(PLAYERS.size).times{ |x|
  progress( subt, x, 'A' )
}
p subt[log2(PLAYERS.size)-1]

実行してみると、すごく遅い。
最初、枝刈りなしで書いてみたらあんまりだったので、枝刈りをちょっと入れてみた。上記ソースに「枝刈り」と書いている場所がそれだ。
n=8 だと、多少枝刈りしているこのアルゴリズムの方が、全く枝刈りせずに馬鹿正直に総当たりするよりもずっと遅い。
n=16 は、実行していないが、正解までたどり着けそうな気がしない。
特に、正解がたくさんあるときにすごく遅くなりそうだと思う。
思うだけで、調べてはいないが。それと。正解が全くないことを検証するのは速いのかもしれないとはちょっと思う。これも思うだけ。

とはいえ。each_combi が遅すぎるという批判は正しいと思う。スタックに積み過ぎ。
それと。この実装が、Cryolite さんの意図にそったものなのかどうか、あまり自信がなかったりする。