140823(3)

Ruby


Partition (number theory)

以下の２つのコードのうち下の方が断然はやい。

n = 6

numbers = (1..n).to_a

cnt = 0

for i in (1..n)

numbers.repeated_combination(i){|j|

  if j.inject(:+) == n

    cnt += 1

  end

}

end

p cnt

n = 6

nums = (1..n).to_a

ps = Array.new(n + 1){0}

ps[0] = 1

nums.each{|num|

  # 末尾がnumなるものをカウント

  (num..n).each{|i|

    ps[i] += ps[i - num]

  }

}

p ps[n]

140823(2)

Ruby


約数の和（自身を含む）

require 'mathn'

# a^1+a^2+......a^x
def sum1(i, j)
  power = 1
  sum = 1
  for k in (1..j)
    power *= i
    sum += power
  end
  return sum
end

# (a^1+a^2+......a^x)(b^1+b^2+......b^y)......
def sum2(i)
  sum = 1
  pq = i.prime_division
  pq.each{|tes| sum *= sum1(tes[0], tes[1])}
  return sum
end

p sum2(24)  # 1, 2, 3, 4, 6, 8, 12, 24

出力結果
60

140823

Ruby


配列の結合について

ary1 = []
for i in (1..8)
p ary1
ary1 |= [2 * i, 3 * i, 5 * i]
end
p ary1

ary2 = []
for i in (1..8)
p ary2
ary2 += [2 * i, 3 * i, 5 * i]
end
p ary2

出力結果
[]
[2, 3, 5]
[2, 3, 5, 4, 6, 10]
[2, 3, 5, 4, 6, 10, 9, 15]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 14, 21, 35]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 14, 21, 35, 16, 24, 40]
[]
[2, 3, 5]
[2, 3, 5, 4, 6, 10]
[2, 3, 5, 4, 6, 10, 6, 9, 15]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25, 12, 18, 30]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25, 12, 18, 30, 14, 21, 35]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25, 12, 18, 30, 14, 21, 35, 16,
 24, 40]

140817

Ruby


gets, each_line, readlines

以下において、Inputは
3776
1111
645
2222
333
とする。

n = gets.to_i
p n
p ""
n = gets.to_i
p n
p ""
ARGF.each_line{|line|
  p line.to_i
}

出力結果
3776
""
1111
""
645
2222
333

n = gets.to_i
p n
p ""
n = gets.to_i
p n
p ""
readlines.each{|line|
  p line.to_i
}

出力結果
3776
""
1111
""
645
2222
333

ARGF.each_line{|line|
  p line.to_i
}

出力結果
3776
1111
645
2222
333

readlines.each{|line|
  p line.to_i
}

出力結果
3776
1111
645
2222
333

140813

Ruby

最大増加部分列（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

140812

Ruby


処理される順番について

すごく基本的なことだが、次の二つは処理される順番が異なる。

def zyunban0(a, p)
  if p > 0
    zyunban0(a, p - 1)
  end
  puts "#{p}: #{a[p]}"
end

a = [100, 101, 102, 103]
b = a.size
zyunban0(a, b - 1)

出力結果
0: 100
1: 101
2: 102
3: 103

def zyunban1(a, p)
  while p > 0
    puts "#{p}: #{a[p]}"
    p = p - 1
  end
end

a = [100, 101, 102, 103]
b = a.size
zyunban1(a, b - 1)

出力結果
3: 103
2: 102
1: 101

140724

Ruby


条件演算子（式が複雑な場合）

「VisualC++2013パーフェクトマスター」で次のコードと出会う。

#include <iostream>
using namespace std;

struct dt1 {
int a;
double b;
};

int main()
{
int a = 1, b;

if (a < 5)
b = 10;
else
b = 50;

b = a<5 ? 10 : 50;

if (a < 10)
b = 1;
else if (a < 100)
b = 2;
else if (a < 500)
b = 3;
else
b = 4;

b = (a < 10) ? 1 : (a < 100) ? 2 : (a < 500) ? 1 : 4;

getchar();
return 0;

}

要するに、赤の部分が条件演算子を使って青の部分のように
1行で書けるということなのだが、
Rubyでも同じようにしてみる。

a = 3
if a < 10
  b = 1
elsif a < 100
  b = 2
elsif a < 500
  b = 3
else
  b = 4
end
puts b

a = 33
if a < 10
  b = 1
elsif a < 100
  b = 2
elsif a < 500
  b = 3
else
  b = 4
end
puts b

a = 333
if a < 10
  b = 1
elsif a < 100
  b = 2
elsif a < 500
  b = 3
else
  b = 4
end
puts b

a = 3333
if a < 10
  b = 1
elsif a < 100
  b = 2
elsif a < 500
  b = 3
else
  b = 4
end
puts b

a = 3
puts b = (a < 10)? 1 : (a < 100)? 2 :(a < 500)? 3 : 4

a = 33
puts b = (a < 10)? 1 : (a < 100)? 2 :(a < 500)? 3 : 4

a = 333
puts b = (a < 10)? 1 : (a < 100)? 2 :(a < 500)? 3 : 4

a = 3333
puts b = (a < 10)? 1 : (a < 100)? 2 :(a < 500)? 3 : 4

出力結果
1
2
3
4
1
2
3
4

140720

Ruby


Hashクラスのsortメソッド？

Ruby 1.9では、Hashクラスのsortメソッドは廃止され、

Hashのキーと値をソートした配列を作成して返す。

i_ary = [4, 1, 3, 2] 

w_ary = ["GABLES", "ANNE", "GREEN", "OF"]

hash = Hash[i_ary.zip(w_ary)]

p hash

p hash.sort

p hash.sort.map{|i| i[1]}.join(" ")

出力結果

{4=>"GABLES", 1=>"ANNE", 3=>"GREEN", 2=>"OF"}

[[1, "ANNE"], [2, "OF"], [3, "GREEN"], [4, "GABLES"]]　　　←配列

"ANNE OF GREEN GABLES"

140713(2)

Ruby


Hashのキーや値をまとめて取り出す。

w = 'a1bxkk3k'

h = w.scan(/[a-z]/).join.chars.group_by(&:to_sym)

p h

p h.keys

p h.map{|f| f.first}　　　　　　　　　　　　　　　　　←これでもＯＫ

p h.values

p h.map{|f| f.last}　　　　　　　　　　　　　　　　　←これでもＯＫ

出力結果

{:a=>["a"], :b=>["b"], :x=>["x"], :k=>["k", "k", "k"]}

[:a, :b, :x, :k]

[:a, :b, :x, :k]

[["a"], ["b"], ["x"], ["k", "k", "k"]]

[["a"], ["b"], ["x"], ["k", "k", "k"]]

140713

Ruby


each_charメソッドは、charsメソッドと同じだが、今のところ後者の方が好きだ。

w = 'a1bxkk3k'

p w.scan(/[a-z]/).join.chars.group_by(&:to_sym)

p w.scan(/[a-z]/).join.each_char.group_by(&:to_sym)

# 途中で切ると…

p w.scan(/[a-z]/).join.chars

p w.scan(/[a-z]/).join.each_char

出力結果

{:a=>["a"], :b=>["b"], :x=>["x"], :k=>["k", "k", "k"]}

{:a=>["a"], :b=>["b"], :x=>["x"], :k=>["k", "k", "k"]}

["a", "b", "x", "k", "k", "k"]

#<Enumerator: "abxkkk":each_char>　　　　　　　　　　　←何か汚い。