分割統治法の中のcounting inversionsを実装してみた

アルゴリズムデザインのゼミでmiyaga50が「counting inversions」について発表していた。

マージソートな考え方を使っているアルゴリズム
協調フィルタリングのようなランキングを使うようなシステムで使われる
嗜好がどれくらい違うかを測る尺度に使える
メタ検索エンジンのようなところでも使える
- 複数の検索エンジンを横断して検索したときにどういうランキング付けをするか、というようなもの
まともにやるとnC2の比較が必要なので、O(n^2)必要なんだけど、マージソート流の分割統治をすることで、O(n logn)で実現する。

で、それをRubyで実装した。p197の付近です。本当はポインタ使ってやらないといけないんだけど、とりあえず面倒なので簡単な例でやってみた。

# -*- coding: utf-8 -*-

def merge_and_count(a, b)
  result = []
  count = 0
  while (a.length > 0 && b.length > 0)
    if(a[0] < b[0])
      result.push a.shift
    else
      result.push b.shift
      count = count + a.length
    end
  end
  if a.length > 0
    result.concat(a)
  elsif b.length > 0
    result.concat(b)
  end
  return {"num" => count, "list" => result}
end

def sort_and_count(l)
  if l.length < 2
    return {"num" => 0, "list" => l}
  else 
    left = (l.length) / 2 
    right = (l.length) / 2
    a = l[0..left-1]
    b = l[right..l.length-1]
    print "[#{l.join(", ")}] was splited into "
    puts "[#{a.join(", ")}] and [#{b.join(", ")}]."

    result_a = sort_and_count(a)
    result_b = sort_and_count(b)

    r_a = result_a["num"]
    r_b = result_b["num"]

    a = result_a["list"]
    b = result_b["list"]
    print "merge [#{a.join(", ")}] and [#{b.join(", ")}] -> "
    merge_result = merge_and_count(a, b)
    puts "[#{merge_result["list"].join(", ")}]"
    r = merge_result["num"]
    l = merge_result["list"]

    puts "r_a : #{r_a}"
    puts "r_b : #{r_b}"
    puts "r : #{r}"
  end
  return {"num" => r_a + r_b + r, "list" => l}
end

a = [7, 3, 6, 5, 1, 2, 4, 8]
puts "Before : [#{a.join(", ")}]"
puts "=" * 50
result = sort_and_count(a)
puts "=" * 50
puts "After : [#{result["list"].join(", ")}]"
puts "Counting Inversions : #{result["num"]}"

実行結果。分割された後に統治がされて行く様子とcountも増えていく様子が分かる。

/tmp% ruby fuga.rb
Before : [7, 3, 6, 5, 1, 2, 4, 8]
==================================================
[7, 3, 6, 5, 1, 2, 4, 8] was splited into [7, 3, 6, 5] and [1, 2, 4, 8].
[7, 3, 6, 5] was splited into [7, 3] and [6, 5].
[7, 3] was splited into [7] and [3].
merge [7] and [3] -> [3, 7]
r_a : 0
r_b : 0
r : 1
[6, 5] was splited into [6] and [5].
merge [6] and [5] -> [5, 6]
r_a : 0
r_b : 0
r : 1
merge [3, 7] and [5, 6] -> [3, 5, 6, 7]
r_a : 1
r_b : 1
r : 2
[1, 2, 4, 8] was splited into [1, 2] and [4, 8].
[1, 2] was splited into [1] and [2].
merge [1] and [2] -> [1, 2]
r_a : 0
r_b : 0
r : 0
[4, 8] was splited into [4] and [8].
merge [4] and [8] -> [4, 8]
r_a : 0
r_b : 0
r : 0
merge [1, 2] and [4, 8] -> [1, 2, 4, 8]
r_a : 0
r_b : 0
r : 0
merge [3, 5, 6, 7] and [1, 2, 4, 8] -> [1, 2, 3, 4, 5, 6, 7, 8]
r_a : 4
r_b : 0
r : 11
==================================================
After : [1, 2, 3, 4, 5, 6, 7, 8]
Counting Inversions : 15