全ての選出と交換に渡る全ての敵の組み合わせを計算 その1

ずうっと前から構想していたのだけれど、バトルファクトリーで選出や交換で変わってくる7戦分の敵のパーティの全ての組み合わせを計算するプログラムを作りたいなあと考えていた。2010/2/22頃にCで愚直に全通り(6C3 * 10^5)試すプログラムを書いたのだけれどもっと高速化したい。

とはいっても実際のファクトリーは複雑なので、まずは単純化した設定で作ってみた。

• 敵は1戦だけ。プレイヤーが選出を決めた後、それと被らないように敵のパーティが決定されるものとする（本当だったら1戦目の敵のパーティはプレイヤーの選出前に決められるのだけれど）
• エントリーの衝突判定が種族とアイテムの二つあるのは複雑なので、衝突判定はエントリーのIDだけによるものとする

require "set"
require_relative "prng.rb"

NUM_ENTRIES = 100
NUM_STARTERS = 6
NUM_PARTY = 3

def main
  starters = (0...NUM_STARTERS).to_a
  p Naive.count(PRNG.new(0), starters)
  p Fast.count(PRNG.new(0), starters)
end

# 枝分かれが起こる要素があったときに初めてそこで枝分かれする方法
module Fast
  module_function
  def count(prng, starters)
    count0(prng, starters, [], [])
  end

  def count0(prng, starters, player_determined, chosen)
    if chosen.length == NUM_PARTY
       return Set.new([chosen])
    end
    x = prng.rand(NUM_ENTRIES)
    if (player_determined + chosen).include?(x)
      # 常にスキップ
      count0(prng, starters, player_determined, chosen)
    elsif not starters.include?(x) or player_determined.length == NUM_PARTY
      # 常に採用
      count0(prng, starters, player_determined, chosen + [x])
    else
      # プレイヤーがxを持っていてスキップする場合
      result1 = count0(prng.dup, starters, player_determined + [x], chosen)
      # 採用する場合
      result2 = count0(prng.dup, starters, player_determined, chosen + [x])

      result1 + result2
    end
  end
end

# 素朴にすべての選出を試す方法
module Naive
  module_function
  def count(prng, starters)
    set = Set.new
    starters.combination(NUM_PARTY).each do |player|
      p = prng.dup
      enemy = choice_enemy_party(player, p)
      set.add enemy
    end
    set
  end

  def choice_enemy_party(player, p)
    result = []
    while result.length < NUM_PARTY
      x = p.rand(NUM_ENTRIES)
      if not result.include?(x) and not player.include?(x)
        result.push x
      end
    end
    result
  end
end

main() if $0 == __FILE__

Fast版は引数のprngを破壊していることやplayer_determinedという変数名が気になるけれど、なかなか綺麗に書けた気がします