何か再帰的な問題はないかと思って、一つ思い出した。「確率のはなし」(p.78) の中にでてきた「パスカルの三角形」。高校の数学の授業でちらっと目にした覚えが。(@_@;)この三角形の作り方は単純なルールに基づいている。まず最上段に1を配置する。それより下の行はその位置の右上の数と左上の数の和を配置する。例えば、5段目の左から2番目には、左上の1と右上の3の合計である4が入る。
パスカルの三角形 - Wikipedia via kwout
方法を考える
それぞれの段の「数のリスト」を得たいと考えたとき、どうやって実装すればいいのだろうか？まずは、要素の少ないものから並べて順に考えていく。
- 1 → [1]
- 2 → [1,1]
- 3 → [1,2,1]
- 4 → [1,3,3,1]
うーん、、、(@_@;)
上記のように「段数」を表わす数値を渡したら、リストが返ってくる関数の名前を pascal と名付け、とりあえず外観だけを書くと、
pascal :: Int -> [Int]
自明な要素
再帰的な定義の必要のない自明なところからはじめる。段数は最初を 0 段と数えることにして、
pascal 0 = [1] pascal 1 = [1,1]
問題はここから。何をどうやって再帰的な関数の呼出しの構造にするのだろうか… ^^;
再帰的な定義
再帰的な構造を考える際のポイントは、「現在 (対象) の構造を、一つ前の構造からどのようにして導くことができるのか？」をチェックすること。例えば、今「1, 4, 6, 4, 1」を見ているとしたら、一つ前の「1, 3, 3, 1」をながめる。
- 1, 3, 3, 1
- 1, 4, 6, 4, 1
「1, 4, 6, 4, 1」 は、1 と 1 で [4, 6, 4] がサンドイッチにされたリストと見ることができる。そして、[4, 6, 4] は、一つ前の [1, 3, 3, 1] から何らかの操作をすることによって作ることができるリスト。「何らかの操作」というのは、以下の部分に限って言えば、
- [1, 3, 3, 1]
- [4, 6, 4]
i 番目の要素を得るのに、前のリストの i 番目と i+1 番目の要素を足し合わせること。
上記のリスト全体に戻って考えると、4 段目 (一番を 0 段と数えた場合) の i 番目の要素は、 3段目の i-1 番目の要素と i 番目を足したもの。ただし、`1’ でサンドイッチされた部分についてのみの話。
これを一般的に言えば、n 段目の i 番目の要素は、pascal (n-1) の i-1 と i 番目を足したものということ。「ただし」以降の記述は上記と同じ。
あ～、とは言ったものの、これをどうやって実装するのだろう…。頭の中が混乱してきた。(@_@;)
Haskell で実装
リストの隣り合った要素を足す関数
一つ一つ別腹で考えることに。名前は、take2sum とでも付けることにして、まずははじめに取り上げた、前の段の要素を足してく関数について考える。
- [1, 1] → [2]
- [1, 2, 1] → [3, 3]
- [1, 3, 3, 1] → [4, 6, 4]
これは特に今回に限ったものでなくて、一般的に数値のリストが与えられたときの話として考えると、例えば、
- [1, 2, 3, 4, 5] → [3, 5, 7, 9]
これの最も単純なケースは、上記に書いたように二つの要素のリストが与えられたとき。つまり、
- [x, y] → [x+y]
要素が一つのリストの場合は、空を返しておくとして、問題は 3 つ以上要素が与えられた場合。しかし、これも単純に
- 先頭の要素を取り出し、残りの要素の先頭と足す。
- 先頭の要素以外は、再帰的に関数を適用。
と考えれば、次のように書ける。
take2sum (x:xs) = (x + head xs) : take2sum xs
上記は、二つの要素を与えた場合でも、「要素が一つのとき空を返す」ようにしておけば、
take2sum [1,2] take2sum (1:2) = (1 + head 2) : take2sum [2] take2sum (1:2) = 3 : [] take2sum (1:2) = 3
というように計算が進められ、結局、要素が二つの場合の定義を書かなくても済む。
リストの末尾には空リストがあるので、イメージとしては要素が二つのときは 3 つの要素を対象にしているような想像をするのがいいのかもしれない。自分の場合は、最初に理解しやすいように、
take2sum [x,y] = [x+y]
の定義を書いておき、take2sum (x:xs) を定義した後に削除するようにしている。すぐには再帰のイメージができないので… ^^;
pascal 関数
次に、上記の関数を利用して pascal 関数を完成させる。n が 1, 2 の場合は先ほど書いたので、3 以上について考えると、
サンドイッチの中身は、一つ前の pascal 関数に、take2sum を適用した結果なので、
pascal n = [1] ++ take2sum (pascal (n-1)) ++ [1]
両端を [1] でサンドイッチし、中身は一つ前の pascal 関数を呼出し、それに先ほどの take2sum 関数を適用。上記によって、これも n = 2 の場合を兼ねることができている。計算の過程を追ってみると、
pascal 1 = [1] ++ take2sum(pascal 0) ++ [1] pascal 1 = [1] ++ take2sum([1]) ++ [1] pascal 1 = [1] ++ [] ++ [1] pascal 1 = [1,1]
完成
全体を示す。
pascal :: Int -> [Int] pascal 0 = [1] pascal n = [1] ++ take2sum (pascal (n-1)) ++ [1] take2sum :: Num a => [a] -> [a] take2sum [x] = [] take2sum (x:xs) = (x + head xs) : take2sum xs main = print $ pascal 4
実行すると結果は、
[1,4,6,4,1]
別解
take2sum 関数のところは、zip とリスト内包表記を使っても書けるので、
pascal :: Int -> [Int]
pascal 0 = [1]
pascal n = [1] ++ take2sum (pascal (n-1)) ++ [1]
where
take2sum xs = [x+y | (x,y) <- zip xs (tail xs)]
main = print $ pascal 10
この場合、take2sum の引数に渡される型が pascal 関数の引数の型が指定してあることより、[Int] であるはずなので、関数の型は書かなくてもいいかな。
上記を実行した結果は、
[1,10,45,120,210,252,210,120,45,10,1]
パスカルの三角形 – Wikipedia と見比べてみると、ちゃんと計算できているようだ。 ^^
無名関数を使って
take2sum なんて名前を消したければ、無名関数を使って、
pascal :: Int -> [Int]
pascal 0 = [1]
pascal n = [1] ++
(\xs -> [x+y | (x,y) <- zip xs (tail xs)]) (pascal (n-1))
++ [1]
うーん、これは… (@_@;)
Python で実装
せっかくなので Python でも実装してみる。上記のリスト内包表記を使った方を真似すると、
def take2sum(xs):
return [x+y for x,y in zip(xs, xs[1:])]
def pascal(n):
if n == 0: return [1]
else:
return [1] + take2sum(pascal(n-1)) + [1]
print pascal(10)
無名関数を使うと、
def pascal(n):
if n == 0: return [1]
else:
return [1] + \
(lambda xs:[x+y for x,y in zip(xs, xs[1:])])(pascal(n-1)) \
+ [1]
うーん… ^^;
Ruby で実装
Haskell, Python と違い、Ruby の zip は相手がいない場合、nil をくっつけるので nil? のチェックが必要。(cf. Python の zip と map の違い)
def take2sum(xs)
result = []
xs.zip(xs[1..xs.length-1]) do |ary|
result << ary[0]+ary[1] unless ary.any?{|e| e.nil?}
end
result
end
def pascal(n)
if n == 0
[1]
else
[1] + take2sum(pascal(n-1)) + [1]
end
end
p pascal(10)
0コメント:
コメントを投稿