関数型プログラミングの初級問題-27問目- 「グループ分け」
プログラミング初心者が挑戦する関数型プログラミングによるリスト操作の練習問題の27問目です。問題は、OCaml公式ページのものを使いました。
内容は、問題と答案です。答案の作成時間は、2時間でした。
問題27.
リストの要素を互いに素な集合に分ける関数groupを書け。（引数に素な集合の各基数のリストが与えられます）
6人を三人組、二人組、余りに組分けする方法は？
※ 例えば、group ["a"; "b"; "c"] [2; 1]は、a, b, cの三文字を二文字の組と一文字の組に組分けするものであり、[[["a"; "b"]; ["c"]]; [["a"; "c"]; "b"]; [["b"; "c"]; "a"]]になります。
答案
本答案のプログラムの作り方
前回の答案で作成した関数extractを使い回します。extractは、リストからk個の要素を「順序を問わず、かつ重複を許さず」に選び出すものです。
今回も「関数型プログラミング」としての解き方がよく分かりませんでした。なので、解の条件から逆算してプログラムを作成しました。
基本的な発想（体裁を整えるためと文字数を稼ぐための文章なので読む価値は薄いです）
プログラムの基になる考え方は以下の二つです。
・関数extractにより生成される入れ子リストの要素は、互いに素である
・extractの再帰呼び出しごとに引数のリストから返り値を引くことで互い素な要素からなるリストが生成される
以下に所与のリストをn要素の組とm要素の組に分ける場合を例に説明します。
まず、n要素の組（孫リスト）からなるリスト（子リスト）を関数extractにより生成します。
extractは「順序を持たず、かつ重複がない」要素数nのリストを全て列挙するので、ちょうどn要素の組の子リストが生成されることになります。
次にm要素の組（孫リスト）からなる子リストを生成します。
m要素の組は、n要素の組との要素の重複が許されません。
そこで、所与のリストからn要素の組を引いて、その差からm要素の組の子リストを生成します。
m要素の子リストの生成は、上述したn要素の子リストの生成する方法と同様にextractにより行います。
以上の手順を子リストについて再帰的に構成します。
さらに、上述の説明では、n要素とm要素の二つの要素数について説明しましたが、本来これらの要素数はリストで与えられます。
そこで、この要素数のリストについても再帰的に構成します。
再帰的に構成します、では説明になっていませんが、再帰的に構成します。
コード
let rec append youso = function [] -> []
| head::tail -> (youso::head)::append youso tail
let rec nest = function [] -> []
| head::tail -> [head]::nest tail
let rec extract n lisuto =
if n = 1 then nest lisuto
else match lisuto with [] -> []
| head::tail -> append head (extract (n-1) tail)@(extract n tail)
---------------------------------------------------------------------------------------
let rec combine lisuto kumi =
let rec prod lisuto = function [] -> []
| head::tail -> (lisuto::head)::(prod lisuto tail) in
let rec remove lisuto =
let rec remove_one youso = function [] -> []
| head::tail ->
if head = youso then (remove_one youso tail)
else head::(remove_one youso tail) in
function
| [] -> lisuto
| head::tail -> remove (remove_one head lisuto) tail in
function [] -> []
| head::tail -> prod head (group (remove lisuto head) kumi)@combine lisuto kumi tail
and group lisuto =
function [] -> [[]]
| head::tail -> combine lisuto tail (extract head lisuto)
線より下の部分が、今回の答案で書いたコードになります。
関数prodは、第1引数のリストと第2引数のリストの要素を掛け合わせたリストからなるリストを返します。
関数removeは、第1引数のリストから第2引数のリストを引いた残りのリストを返します。
関数combineは、関数groupとともに定義された相互再帰関数です。
感想
今回も解き方の説明はありません。直観のままにコードを書きました。
これが試験だとすると、途中式がないので0点になるでしょう。
かと言って、ネットでよく見かけるプログラムを日本語に直訳したものを説明と称するのもバカらしいです。
そもそもコードを読めば分かることを、言い換える必要があるのでしょうか？
もし読めないコードを書いているならば、その無駄な労力をコードの改善にこそ注ぐべきです。
ああ耳が痛い。
次回は、第28問です。前回は、自信満々に答案を書いておきながら間違っていました。今回は、自信がないのでおそらく正解しているでしょう。
古往今来得ざれば即ち書き得れば即ち飽くは筆の常也。と云うわけで御座います、この浅ましき乞食めに何卒皆々様のご慈悲をお願い致します。