« 4変数の順序関係はいくつあるか? | トップページ | エンジニア「超」促成栽培 »

2008年3月22日 (土)

順序関係を列挙する

先日のエントリ 4変数の順序関係はいくつあるか? の続きです。

順序関係を列挙するプログラムを、Ruby で作成してみます。

順列と組合せ

教科書のタイトルみたいですが。これが基本操作になりますので、初めに作成します。

順列を作るメソッド permutate を定義します。このメソッドは、配列 src_a と整数 rib_i を受け取って、順列の配列を戻します。これは、src_a から rib_i 個をとる順列を作ります。順に要素をひとつ取得し、取得した要素を除いた配列からまた取得、とすればよろしいかと思います。

def permutate_it(src_a, dst_a, rib_i, res_a)
  if rib_i == 0 || src_a.size == 0
    res_a.push dst_a
  else
    src_a.each do |src|
      permutate_it(
      src_a - [src], dst_a + [src], rib_i - 1, res_a)
    end
  end
  res_a.size
end

def permutate(src_a, rib_i)
  res_a = []
  permutate_it(src_a, [], rib_i, res_a)
  res_a
end

以下のように実行します。

irb(main):007:0> permutate([:x1, :x2, :x3], 2)
=> [[:x1, :x2], [:x1, :x3], [:x2, :x1], [:x2, :x3], [:x3, :x1], [:x3, :x2]]
irb(main):008:0> permutate([:x1, :x2, :x3], 2).size
=> 6

組合せを作るメソッド combine を定義します。順列メソッドとほぼ同じですが、組合せの場合、取得した要素よりも前の位置にある要素からは取得しません。常に次以降の要素から取ります。

def combine_it(src_a, dst_a, rib_i, res_a)
  if src_a.size < rib_i
    # nothing.
  elsif rib_i == 0 || src_a.size == 0
    res_a.push dst_a
  else
    src_a.each_index do |i|
      combine_it(
      src_a[i + 1, src_a.size - i - 1],
      dst_a + [src_a[i]], rib_i - 1, res_a)
    end
  end
  res_a.size
end

def combine(src_a, rib_i)
  res_a = []
  combine_it(src_a, [], rib_i, res_a)
  res_a
end

以下のように実行します。

irb(main):009:0> combine([:x1, :x2, :x3], 2)
=> [[:x1, :x2], [:x1, :x3], [:x2, :x3]]
irb(main):010:0> combine([:x1, :x2, :x3], 2).size
=> 3

不等号、等号、不存在

それぞれのメソッドを定義します。不等号の場合 case_inequal は、単に順列を作成するだけです。等号の場合は case_equal は、2個以上の組合せをまず作成し、元の配列からその要素を除き、1要素として追加した後、不等号の場合を適用します。不存在の場合 case_exist は、1個以上の組合せを作成し、元の配列から除いた後、不等号の場合、等号の場合をそれぞれ適用し、足し合わせます。

def case_inequal(src_a)
  permutate(src_a, src_a.size)
end

def case_equal(src_a)
  res_a = []
  (2 .. src_a.size).each do |r|
    combine(src_a, r).each do |c|
      p_a = [c] + src_a - c
      res_a += case_inequal(p_a)
    end
  end
  res_a
end

def case_exist(src_a)
  res_a = []
  (1 .. src_a.size).each do |r|
    combine(src_a, r).each do |c|
      p_a = src_a - c
      res_a += case_inequal(p_a)
      res_a += case_equal(p_a)
    end
  end
  res_a
end

すべてを列挙

等号、不等号、不存在の各メソッドを順に適用し、足し合わせます。

def gen_norder(src_a)
  res_a = case_inequal(src_a)
  res_a += case_equal(src_a)
  res_a += case_exist(src_a)
  res_a
end

以下が実行結果です。

irb(main):012:0> gen_norder([:x1, :x2, :x3, :x4]).size
=> 144
irb(main):013:0> i = 0; gen_norder([:x1, :x2, :x3, :x4]).each { |v| print("#{i += 1}:"); p v }
1:[:x1, :x2, :x3, :x4]
2:[:x1, :x2, :x4, :x3]
3:[:x1, :x3, :x2, :x4]

...

133:[[:x1, :x4]]
134:[:x1, :x3]
135:[:x3, :x1]
136:[[:x1, :x3]]
137:[:x1, :x2]
138:[:x2, :x1]
139:[[:x1, :x2]]
140:[:x4]
141:[:x3]
142:[:x2]
143:[:x1]
144:[]

配列の中に配列があるものは、その要素が”等しい”の意になります。

|

« 4変数の順序関係はいくつあるか? | トップページ | エンジニア「超」促成栽培 »

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: 順序関係を列挙する:

« 4変数の順序関係はいくつあるか? | トップページ | エンジニア「超」促成栽培 »