Haskellで上位者問題を解く
酒の神「バッカス」
おはようございます。
しょうがないからBlack日課飲んでます。
こういう世の中なんですよ今の日本は。
資本主義と見せかけて社会主義っぽくもある気持ち悪さ。
そして根本的な教育の方針の欠陥。
大学とかこういう場に来て尚実感してこういう感想に至った次第です。
この国は終わりです。海外へ逃げる準備をした方がいいですよ皆さん。
色々な信念とか思想を人々はもっていますけれでも、
先入観とか言ったイドラは違います。これは良くないです。
「人間思ったほど客観視出来てはいない」それはそうですが、だから諦めるのか？という感じではあります。
冷静になって自分を切り離して客観視する努力は必要なのであります。
まぁせめてProkrustesbettのあやまちを犯さないようにしたい。
生きろ
最近生きながらにして死んでいる人が多い気がする。
ケルケゴールは「死に至る病」で、
「無自覚者も死に至る病を患う」といっています。
でもでも、無自覚者って、本人の感覚としては、
絶望を知らないんですから、とても幸せなんだと思いますけど。
いやでも、「人間は動物より勝っているからこそ、言いかえれば人間は自己であり精神であるからこそ、絶望することができるのである」
かもしれませんね。
人間の生きる骨は「愚鈍さ」と「慣れ」な気がしてきましたからね。
そもそも人間ってなんだろうって思うけれども、
「最低限の理性と、知的好奇心とか、精神を持っていて魂が輝いている生物」
こんな定義をしたら個人的にこの眼で見て人間だなと感じた人は少ない。
まぁこれは人間はこう有るべきみたいな、私の個人的な理想像でもあるので、
あんまり気にしないでくださいというか、些か強引すぎますかねぇ。
御託はいいから講釈垂れてよ
このフレーズは「げんがくさばいば」さんから拝借しました。
私の尊敬する人の一人です。
title的に考えますと今回は「Haskellで上位者問題を解く」ですね。
まぁ前々回のブログでも書きましたけど、
今読んでる「関数プログラミング珠玉のアルゴリズムデザイン」って本の内容そのままです。
これです。
今回は第二章です。
「上位者問題」ってご存知でしょうか。
説明いたしますと、配列の一つの要素に対して、その上位者とは、
その要素の右側に有り、その要素より大きい要素をいいます。
つまり、上位者は配列x[]で「かつ
」ですかね。
例えば「APPLE」という文字列で考えた時に、
A;0,B;1..といったふうに割り当てた時、
それぞれの文字の持つ上位者の数、上位者数は、
[('A',4),('E',0),('L',0),('P',0),('P',0)]
となります。この場合、最大値はAの4となります。
こういったふうにして、文字列の最大上位者数を求めていきます。
当たり前だけどHaskellでな
今回もHaskellで、しかも分割統治法を使います。
皆さんの身近な分割統治法の例ですと、「クイックソート」とかそうですね。
問題を小さくして、その小さい問題を解いて元の大きさの問題を解いたことにする、というものだと思ってます。
まぁみなさんは生まれながらにしてHaskellはわかると思うので大丈夫でしょう。
以下がコードです。
import Data.List join 0 txs [] = txs join n [] tys = tys join n txs@((x,c) : txs') tys@((y,d) : tys') | x < y = (x,c+n) : join n txs' tys | x >= y = (y,d) : join (n-1) txs tys' table [x] = [(x,0)] table xs = join (m-n) (table ys) (table zs) where m = length xs n = m `div` 2 (ys,zs) = splitAt n xs msc s = maximum $ map snd (table s)
これはさっきもいいましたが、
「文字列の最大上位者数」を求めます。
その関数はmscですね。msc (文字列)という風にご利用ください。
msc関数を説明しますと、その引数(s)をまずtable関数で受けます。
table関数はタプルにして、各文字とその上位者数の組にして、
その全部をリストにして返します。
table関数はO()らしいです。
となると当然mscも同じくそうなることがわかりますね。
終わりです。投げやりかもしれませんね。すみません、
ではでは。
