F# 雑記 昇順になる部分列の長さの最大
BLUEPIXYさんのブログでとりあげられた問題を、自分でもやってみました。 
問題は数列の部分列（条件：昇順になっていること）のうち、最大の長さをもつものの長さを求めよというものです。
F#でリストを使ってやってみます。
一つ目は最大の長さをもつものの内の一つを返す関数を定義します。
> //最長のリストの長さを求める関数
let getLongestLst lstlst =
if List.length lstlst = 0 then
[]
else
List.reduce (fun ele1 ele2 -> if List.length ele1 > List.length ele2 then ele1 else ele2) lstlst
//nを付け足せるもののうち最長のリストにnを付け足した形で返す関数。
let getlongestNhead n lstlst =
let underNheadLsts = List.filter (fun lst -> List.head lst < n) lstlst
let longest= getLongestLst underNheadLsts
n :: longest
//最長の増加部分列のうち一つを返す関数
let rec getAns rem res =
match rem with
|hd::tl -> getAns tl ((getlongestNhead hd res)::res)
|[] -> getLongestLst res |> List.rev ;;
val getLongestLst : 'a list list -> 'a list
val getlongestNhead : 'a -> 'a list list -> 'a list when 'a : comparison
val getAns : 'a list -> 'a list list -> 'a list when 'a : comparison
使ってみます。
> getAns [33;1;22;3;34;6;54;9;19] [];;
val it : int list = [1; 3; 6; 9; 19]
もう一つは、最長のものの長さだけ返します。
> let rec search cnt lastAddedNum rem =
match rem with
|[] -> cnt
|hd::tl when hd > lastAddedNum -> max (search cnt lastAddedNum tl) (search (cnt+1) hd tl)
|hd::tl -> (search cnt lastAddedNum tl);;
val search : int -> 'a -> 'a list -> int when 'a : comparison
使ってみます。
> search 0 System.Int32.MinValue [33;1;22;3;34;6;54;9;19];;
val it : int = 5
コメントの投稿
ちょっとだけコメント
リストの長さは、０未満にはなり得ないのだから、
System.Int32.MinValue とかでなく、
単に−１でいいんじゃないかと思いますけど。
（好きずきかな）
System.Int32.MinValue とかでなく、
単に−１でいいんじゃないかと思いますけど。
（好きずきかな）
No title
System.Int32.MinValue が入っているのは直前にリストに加えられた数のところなので、数列が負の数を含む場合も大丈夫なようにSystem.Int32.MinValue にしました。
> search 0 System.Int32.MinValue [-2;1;2];;
val it : int = 3
> search 0 -1 [-2;1;2];;
val it : int = 2
となってしまいます。
> search 0 System.Int32.MinValue [-2;1;2];;
val it : int = 3
> search 0 -1 [-2;1;2];;
val it : int = 2
となってしまいます。
sorry
大小関係が比べられるオブジェクトのその時々の最小のものを渡すってことですね。
勝手にリストの長さだと思い込んでました。
ぼけたことをいってすみません。
m(_ _)m
勝手にリストの長さだと思い込んでました。
ぼけたことをいってすみません。
m(_ _)m
