書いてみた

昨日の続き。
http://www.kmonos.net/wlog/53.php#_1604050908 の、トーナメントひいき問題。
紙とペンで考えてもわからないので、とりあえずプログラムを書いてみた。
まずは、総当たり方式（←バカ）。
ここで haskell で書くのが筋のように思えるが、やっぱり ruby。

require 'set'

L = {
  'A' => [ '', 'o', 'x', 'x', 'o', 'x', 'o', 'x' ],
  'B' => [ 'x', '', 'o', 'x', 'x', 'o', 'x', 'x' ],
  'C' => [ 'o', 'x', '', 'o', 'o', 'o', 'o', 'x' ],
  'D' => [ 'o', 'o', 'x', '', 'o', 'o', 'o', 'o' ],
  'E' => [ 'x', 'o', 'x', 'x', '', 'x', 'x', 'x' ],
  'F' => [ 'o', 'x', 'x', 'x', 'o', '', 'x', 'x' ],
  'G' => [ 'x', 'o', 'x', 'x', 'o', 'o', '', 'o' ],
  'H' => [ 'o', 'o', 'o', 'x', 'o', 'o', 'x', '' ],
}

PLAYERS = L.keys

table=Hash.new{ Set.new }

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

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
    table[ x ] += y
  elsif ywin
    table[ y ] += x
  else
    raise "unexpected."
  end
}

Table = table

def target_lost( c, target )
  return ( if c.flatten.include? target
    target != find_winner( c )
  else
    false
  end )
end


def each_tment( players, target )
  if players.size==1 then
    yield players
  else
    tail = players[ 1..-1 ]
    each_combi( tail, players.size/2 ){ |c1|
      c0 = players-c1
      each_tment(c0, target){ |x0|
        next if target_lost( x0, target ) 
        each_tment(c1, target){ |x1|
          next if target_lost( x1, target ) 
          yield [x0,x1]
        }
      }
    }
  end
end

def find_winner( x )
  case x
  when Array
    case x.size
    when 1
      find_winner( x[0] )
    else
      w = x.map{ |i| find_winner( i ) }
      (0..1).each{ |m|
        return w[m] if Table[w[m]].member?( w[1-m] )
      }
      raise "#{w.join(',')} : not found in Table"
    end
  else
    x
  end
end

each_tment(PLAYERS, 'A'){ |x|
  winner = find_winner( x )
  if winner=='A'
    puts( '%s => %s' % [ x.inspect, winner ] )
    exit
  end
}

総当たりと書いたが、「target_lost」を呼んでいるところで枝刈りをしている。
8人ぐらいでは枝刈りをしなくても一緒か、かえって遅いくらいなんだが、16人になると、計算が終わるか否かの決定的な要因になる。

乱数で問題を作ってみると、解がある場合については、16人でもだいたい10秒以下で計算が終わる。
解がない場合は、10分待っても終わらないのでそのまま寝たら、朝には終わっていた。時間は計ってない。

まだ実装していないが、枝刈りのできる既知のポイントがもう一つある。
それは。残り試合が n のとき、ターゲットとの距離（ターゲット自身は距離ゼロ。ターゲットに負ける人は距離1。距離n未満でなく、距離n-1の人に負ける人は距離n、と、定義する）が n+1 以上の人がいたら調査しない、というものだ。
これで、全勝の人がいたりした場合に諦めることができるようになる。

いや、それでもまだ足りない。
16人プレイヤーがいるときに、ターゲットが3人にしか勝てないケースが刈れていない。

と、枝刈りをあと2種類ぐらい実装すれば、いい線まで行けるんじゃないかと思っているんだが、数学を背景にしたきれいな実装ではないので、計算量を見積もるのは困難である。

それと。
id:Cryolite:20050908:p3 も、自分で実装してみるつもり。枝刈りも入れて。まだよく読んでないが。
＃pruning って何?　と思って辞書をあたると、枝刈りだった。あう。