最大増加部分列（longest increasing subsequence）
「Rubyによる情報科学入門」で最大増加部分列の問題と出会う。
以下のコード（http://133.11.50.227/~kuno/is11/siryou/ohp12.pdf）
に間違いを見つける。
def lis(a)
l = Array.new(a.length); t = Array.new(a.length)
m = 1; p = 0
a.each_index do |i|
l[i] = 1; t[i] = i+1
(i-1).step(0, -1) do |j|
if a[i] > a[j] && l[i] < l[j]+1
l[i] = l[j]+1; t[i] = i-j
if m < l[i] then p = i; m = l[i] end
end
end
end
puts "a: #{a}" #コードの間違いを発見するために追加
puts "l: #{l}" # 〃
puts "t: #{t}" # 〃
showlis(a, t, p); puts
end
def showlis(a, t, p)
if p > 0 then showlis(a, t, p-t[p]) end
print(" #{a[p]}")
end
# 実験
a = [1, 5, 7, 2, 6, 3, 4, 9]
lis(a)
b = [4, 1, 6, 2, 8, 5, 7, 3]
lis(b)
c = [4, 1, 6, 2, 8, 0, 5, 7, 3]
lis(c)
d = [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]
lis(d)
出力結果
a: [1, 5, 7, 2, 6, 3, 4, 9]
l: [1, 2, 3, 2, 3, 3, 4, 5]
t: [1, 1, 1, 3, 1, 2, 1, 1]
1 2 3 4 9
a: [4, 1, 6, 2, 8, 5, 7, 3]
l: [1, 1, 2, 2, 3, 3, 4, 3]
t: [1, 2, 1, 2, 1, 2, 1, 4]
3 1 2 5 7
a: [4, 1, 6, 2, 8, 0, 5, 7, 3]
l: [1, 1, 2, 2, 3, 1, 3, 4, 3]
t: [1, 2, 1, 2, 1, 6, 3, 1, 5]
3 1 2 5 7
a: [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]
l: [1, 1, 2, 2, 3, 1, 3, 4, 3, 2, 3, 4, 5]
t: [1, 2, 1, 2, 1, 6, 3, 1, 5, 4, 1, 1, 1]
4 0 1 2 3 4
修正
def lis(a)
l = Array.new(a.size); t = Array.new(a.size)
m = 1; p = 0
a.each_index{|i|
l[i] = 1; t[i] = 0
(i - 1).step(0, -1){|j|
if a[i] > a[j] && l[i] < l[j] + 1
l[i] = l[j] + 1; t[i] = i - j
if m < l[i]
p = i; m = l[i]
end
end
}
}
puts "a: #{a}"
puts "l: #{l}"
puts "t: #{t}"
showlis(a, t, p); puts
end
def showlis(a, t, p)
if t[p] > 0
showlis(a, t, p - t[p])
end
print(" #{a[p]}")
end
a = [1, 5, 7, 2, 6, 3, 4, 9]
lis(a)
b = [4, 1, 6, 2, 8, 5, 7, 3]
lis(b)
c = [4, 1, 6, 2, 8, 0, 5, 7, 3]
lis(c)
d = [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]
lis(d)
出力結果
a: [1, 5, 7, 2, 6, 3, 4, 9]
l: [1, 2, 3, 2, 3, 3, 4, 5]
t: [0, 1, 1, 3, 1, 2, 1, 1]
1 2 3 4 9
a: [4, 1, 6, 2, 8, 5, 7, 3]
l: [1, 1, 2, 2, 3, 3, 4, 3]
t: [0, 0, 1, 2, 1, 2, 1, 4]
1 2 5 7
a: [4, 1, 6, 2, 8, 0, 5, 7, 3]
l: [1, 1, 2, 2, 3, 1, 3, 4, 3]
t: [0, 0, 1, 2, 1, 0, 3, 1, 5]
1 2 5 7
a: [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]
l: [1, 1, 2, 2, 3, 1, 3, 4, 3, 2, 3, 4, 5]
t: [0, 0, 1, 2, 1, 0, 3, 1, 5, 4, 1, 1, 1]
0 1 2 3 4
0 件のコメント:
コメントを投稿
注: コメントを投稿できるのは、このブログのメンバーだけです。