続・深さ優先探索

先日の記事でバックトラック法が上手く書けない、と焦っていましたが、デザインをきちんとやったらすんなり書けました。今回は動作に対してもそれなりに納得できるものになりましたので、一応転記しておきます。
やっていることは単純で、こんな組合せを作ります。

• 制約条件
  1. :q1 は :s1, :s2 のいずれかを選択する。
  2. :q2 は :s2, :s3 のいずれかを選択する。
  3. :q1, :q2 は必ず選択されなくてはならない。
  4. :s1, :s2, :s3 は１回だけ選択可能。
• 結果
  1. [{:q2=>:s2}, {:q1=>:s1}]
  2. [{:q2=>:s3}, {:q1=>:s1}]
  3. [{:q2=>:s3}, {:q1=>:s2}]

irbで実行するとこんな感じです。

irb(main):139:0> constraint = CMB::CmbConstraint.sample
=> {:q2=>[:s2, :s3], :q1=>[:s1, :s2]}
irb(main):140:0> CMB::CmbCreator.create constraint
=> [[{:q2=>:s2}, {:q1=>:s1}], [{:q2=>:s3}, {:q1=>:s1}], [{:q2=>:s3}, {:q1=>:s2}]]

以下、コード。Railsで使うつもりでしたので、クラス名にCmbという接頭辞を付けています。ダサイです。バックトラック法を用いていますので、Haskilなどの関数型言語で記述するともう少しマシになるかもしれません。

module Combination
  # hash of 'key => array'
  # { q1 => [s11, s12, ...], q2 => [s21, s22, ...] }
  class CmbConstraint < Hash
    def self.sample
      hash = {:q1=>[:s1, :s2], :q2=>[:s2, :s3]}
      self.create hash
    end
    
    def self.create(hash)
      ret = self.new
      hash.each do |key, ary|
        ret[key] = ary.dup
      end
      ret
    end

    # 破壊的
    def delete_pair!(q, s)
      delete(q)
      each do |key, ary|
        ary.delete(s)
      end
      self
    end

    def delete_pair(q, s)
      ret = self.class.create(self)
      ret.delete_pair!(q, s)
    end
  end

  class CmbCell < Hash
    def self.make(q, s)
      cell = self.new
      if cell.empty?
        cell[q] = s
      else
        raise "CmbCell has an only member"
      end
      cell
    end
  end

  class CmbRow < Array
    # 破壊的
    def add_cell!(cell)
      self << cell
    end
    
    # 非破壊的
    def add_cell(cell)
      ret = self.dup
      ret.add_cell!(cell)
    end
  end

  class CmbTable < Array
    def self.make(*rows)
      table = self.new
      rows.each do |row|
        table << row
      end
    end

    # Arrayにて定義済だが、再定義が必須
    def +(other)
      ret = self.dup
      other.each do |item|
        ret << item
      end
      ret
    end
  end

  class CmbCreator
    def self.create(constraint, row = CMB::CmbRow.new)
      creator = self.new
      constraint = CMB::Cmbconstraint.create(constraint) unless constraint.kind_of? CMB::Cmbconstraint
      creator.create(constraint, row)
    end
    
    # constraint: CmbConstraint
    # row:  CmbRow
    # retrun: CmbTable
    #   Array of CmbRows: [ r1, r2, ... ]
    def create(constraint, row = CMB::CmbRow.new)
      return CmbTable.make(row) if constraint.empty?
      result = CmbTable.new
      q = constraint.keys.first
      for s in constraint[q]
        cell = CmbCell.make(q, s)
        t_constraint = constraint.delete_pair(q, s)
        t_row = row.add_cell(cell)
        t_table = create(t_constraint, t_row)
        result += t_table
      end
      result
    end
  end
end

CMB = Combination