2016年1月3日日曜日

160103(6)

Ruby


Arrangement of the word 'Success'

A190945(100)(2) の二つ目のコードで使っている考え方は
実に汎用性がある。
考え方を知りたい人は以下を読んでみてください。
http://math.stackexchange.com/questions/129451/find-the-number-of-arrangements-of-k-mbox-1s-k-mbox-2s-cdots
http://math.stackexchange.com/questions/162394/arrangement-of-the-word-success

この考え方を用いてコードを書いてみた。
オンライン整数列大辞典の
A114938(http://oeis.org/A114938/list)、
A190945(http://oeis.org/A190945/list)
と比較し、答え合わせしてみる。

def C(n, r)
  r = [r, n - r].min
  return 1 if r == 0
  return n if r == 1
  numerator = (n - r + 1..n).to_a
  denominator = (1..r).to_a
  (2..r).each{|p|
    pivot = denominator[p - 1]
    if pivot > 1
      offset = (n - r) % p
      (p - 1).step(r - 1, p){|k|
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
      }
    end
  }
  result = 1
  (0..r - 1).each{|k|
    result *= numerator[k] if numerator[k] > 1
  }
  return result
end

def mul(f_ary, b_ary)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def f(a)
  ary = [1]
  a.each{|k|
    ary1 = [0]
    (1..k).each{|j|
      ary1 << (-1) ** (k - j) * C(k - 1, k - j) / (1..j).inject(:*).to_r
    }
    ary = mul(ary, ary1)
  }
  s = 0
  (1..ary.size - 1).each{|p|
    s += (1..p).inject(:*) * ary[p]
  }
  s.to_i
end

def A114938(n)
  (1..n).map{|i| f((1..i).map{2})}
end

def A190945(n)
  (1..n).map{|i| f(1..i)}
end

# Arrangement of the word 'Success'
p f([1, 1, 2, 3])

ary = A114938(16)
# OEIS A114938のデータ
ary0 =
[0,2,30,864,39480,2631600,241133760,29083420800,
 4467125013120,851371260364800,197158144895712000,
 54528028997584665600,17752366094818747392000,
 6720318485119046923315200,
 2927066537906697348594432000,
 1453437879238150456164433920000]
# 一致の確認
p ary == ary0

ary = A190945(11)
# OEIS A190945のデータ
ary0 =
[1,1,10,1074,1637124,45156692400,
 27230193578558160,420296434943941609215120,
 190200071567439616748736269178720,
 2843464512159537301384360263178682136716160,
 1562137388408002436396705025296003247844758163480828800]
# 一致の確認
p ary == ary0

出力結果
96
true
true

0 件のコメント:

コメントを投稿