P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.
うーむ…my-combination
を再帰で呼ぶようにしたけど、これ末尾再帰になってないしもっと良い書き方があるように思うなぁ…。
(my-combination 3 '(a b c d e f))
の場合、引数が二つなので
([n xs] (my-combination n xs nil))
つまり(my-combination 3 '(a b c d e f) nil)
が呼ばれる。(range 0 (- (count xs) (dec n)))
は n が 3, xs が '(a b c d e f) の場合、(0 1 2 3)
となる。(drop % xs)
により((a b c d e f) (b c d e f) (c d e f) (d e f))
が作られ、nをデクリメントしてysに選ばれた要素zを追加しながら
my-combination
を再帰で呼ぶ、という事をしている。mapcat
はScalaでいうflatMap
のようなものらしい。P27 (**) Group the elements of a set into disjoint subsets.
9要素を2要素,3要素,4要素ずつに分ける関数my-group3
と、何要素ずつに分けるかを引数で与える関数my-group
を作る。my-group
を作ってから(my-group xs '(2 3 4))
を呼ぶmy-group3
を作ったほうが綺麗だとは思うが、出題の流れとしては
my-group3
を作って、その応用としてmy-group
を作る意図があるように思うので少々汚いながらもベタに
my-group3
を書いた。P26で作った
my-combination
をそのまま利用する。また、リストxsの中に要素xが含まれるかを調べる関数
not-contain?
を定義した。(複数回使用している事もあるが、filterに渡す際にこちらのほうが見通しが良くなるかと考えたため)
my-group3
はまずmy-combination
を呼び2要素選択するパターンを取得し、元のリストから選択された2要素を除いたリストys'に対して再度
my-combination
を呼び3要素選択するパターンを取得する。同じ要領で4要素選択するパターンを取得するためもう一度
my-combination
を呼んでもよかったが、9要素のリストからまず2要素、次に3要素を選択すると残った要素数は4なので、ys'から選択された3要素を除いたリストを作るだけにした。
なので、これに対して要素数9のリスト以外を渡すと正しく動かないはず…横着した。
my-group
は同じような処理を引数nsの要素分だけ再帰で実行し、最終的に返す結果のysに選択したxs'を追加していく、という処理にしている。
こちらも末尾再帰になっていないが…。
P28 (**) Sorting a list of lists according to length of sublists.
前2問とは毛色の異なる問題。再帰などを用いて要素の入れ替えを自力で行う事が求められていたかもしれないが、
sort-by
関数を利用して簡潔に解くことにした。my-lsort
は要素数で昇順ソートなので、count
で比較するだけで良さそうだ。要素数の出現頻度によってソートが必要な
my-lfsort
はもう一捻り必要そう。Project Euler の Problem 62で知ったシュワルツ変換を利用することにした。
(map #(list (count %) %) xss)
で要素数と元の要素のリストを作り、要素数でgroup-by
する。ソート対象のリストが
'((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o))
の場合、この時点で
{3 [(3 (a b c)) (3 (f g h))], 2 [(2 (d e)) (2 (d e)) (2 (m n))], 4 [(4 (i j k l))], 1 [(1 (o))]}
ができる。出現頻度順にソートしたいので
(sort-by #(count (second %))
を行う。この時点で
([4 [(4 (i j k l))]] [1 [(1 (o))]] [3 [(3 (a b c)) (3 (f g h))]] [2 [(2 (d e)) (2 (d e)) (2 (m n))]])
ができる。これでソートは完了しているので、それぞれの元の要素のみ取り出して完了。