« エンジニア「超」促成栽培 | トップページ | 成功を重ねるほどハードルは高くなる »

2008年3月24日 (月)

順序関係列挙と事前条件

さらに続きです。

4変数の順序関係はいくつあるか?

順序関係を列挙する

順序関係の列挙に、事前条件の加味を加えます。以下のように、事前条件を満たさないものを、列挙から除きます。

irb(main):002:0> i = 0; apply_cond(gen_norder([:x1, :x2, :x3, :x4]), [:x1, :x2,:x3, :x4], ['x1<x2', 'x2<x3', 'x3<x4']).each {|v| print("#{i += 1}:"); p v }; nil
1:[:x1, :x2, :x3, :x4]
=> nil

apply_cond メソッドは、第1引数に順序関係の配列、第2引数に結果に必ず含まれるべき変数の配列、第3引数に事前条件の配列を指定して呼び出します。

def apply_cond(src_a, req_a, cond_a)
  res_a = []
  src_a.each do |exp|
    if required_exist?(exp, req_a) &&
      cond?(exp, cond_a)
      res_a.push(exp)
    end
  end
  res_a
end

required_exist? メソッドは、順序関係 src_exp の中に、配列 req_a のシンボルがすべて存在するかをテストします。

def required_exist?(src_exp, req_a)
  target_a = src_exp.flatten
  req_a.each do |v|
    if !target_a.include?(v)
      return false
    end
  end
  true
end

cond? メソッドは、ちょっと強引ですが。まず、順序関係 src_exp の各変数に、配列の添字 + 1 を、 eval で代入します。その後、与えられた条件の配列 cond_a を順に eval します。

def cond?(src_exp, cond_a)
  init_exp = []
  src_exp.each_index do |i|
    v = src_exp[i]
    if v.instance_of?(Array)
      init_exp.push("#{v.join('=')}=#{i+1}")
    else
      init_exp.push("#{v}=#{i+1}")
    end
  end
  eval(init_exp.join(';'))
  cond_a.each do |cond|
    begin
      if !eval(cond)
        return false
      end
    rescue NameError
    end
  end
  true
end

事前条件 x1 < x3, x2 < x4 を与えてみます。

irb(main):003:0> i = 0; apply_cond(gen_norder([:x1, :x2, :x3, :x4]), [], ['x1<x3', 'x2<x4']).each {|v| print("#{i += 1}:"); p v }; nil
1:[:x1, :x2, :x3, :x4]
2:[:x1, :x2, :x4, :x3]
3:[:x1, :x3, :x2, :x4]
4:[:x2, :x1, :x3, :x4]
5:[:x2, :x1, :x4, :x3]
6:[:x2, :x4, :x1, :x3]
7:[[:x1, :x2], :x3, :x4]
8:[[:x1, :x2], :x4, :x3]

...

44:[:x1, :x2]
45:[:x2, :x1]
46:[[:x1, :x2]]
47:[:x4]
48:[:x3]
49:[:x2]
50:[:x1]
51:[]
=> nil

大体、条件をつけない場合の3分の1くらいでしたね。

|

« エンジニア「超」促成栽培 | トップページ | 成功を重ねるほどハードルは高くなる »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/80472/11714337

この記事へのトラックバック一覧です: 順序関係列挙と事前条件:

« エンジニア「超」促成栽培 | トップページ | 成功を重ねるほどハードルは高くなる »