N 個の要素 X を持つリストを生成する関数 make_list(X, N) と、整数 N から M までの値に関数 F を適用した結果をリストに格納して返す関数 tabulate(F, N, M) を定義してください。
> yaep02:make_list(a, 10).
[a,a,a,a,a,a,a,a,a,a]
> yaep02:make_list("hello", 5).
["hello","hello","hello","hello","hello"]
> yaep02:tabulate(fun(X) -> X end, 1, 10).
[1,2,3,4,5,6,7,8,9,10]
> yaep02:tabulate(fun(X) -> X * X end, 1, 10).
[1,4,9,16,25,36,49,64,81,100]
リスト Xs から要素 X をすべて削除する関数 remove(X, Xs) と、述語 Pred が真を返す要素をすべて削除する関数 remove_if(Pred, Xs) を定義してください。
> yaep02:remove(a, [a, b, c, a, b, c, a]). [b,c,b,c] > yaep02:remove_if(fun(X) -> X rem 2 =:= 0 end, [1, 2, 3, 4, 5, 6, 7, 8]). [1,3,5,7]
リスト Xs を平坦化する関数 flatten(Xs) を定義してください。
> yaep02:flatten([a, b, [c, d, [e | f], g], h]). [a,b,c,d,e,f,g,h] > yaep02:flatten([a, b, [c, d, [e, [] | f], g], h]). [a,b,c,d,e,f,g,h]
リスト Xs に格納された複数のリストを連結する関数 concat(Xs) を定義してください。
> yaep02:concat([[a, b, c], [d, e], [f, g, h, i]]). [a,b,c,d,e,f,g,h,i]
リスト Xs に格納されたリストに関数 F を適用し、その結果を連結する関数 flatmap(F, Xs) を定義してください。
> yaep02:flatmap(fun(X) -> [a | X] end, [[b, c], [d, e], [f, g], [h, i]]). [a,b,c,a,d,e,a,f,g,a,h,i]
リスト Xs から N 個の要素を選ぶ順列を求める関数 permutation(N, Xs) を定義してください。
> yaep02:permutation(3, [a, b, c]). [[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]
なお、生成した順列はリストに格納して返すものとします。
リスト Xs から重複を許して N 個の要素を選ぶ順列を求める関数 repeat_perm(N, Xs) を定義してください。なお、生成した順列はリストに格納して返すものとします。
> yaep02:repeat_perm(2, [a, b, c]). [[a,a],[a,b],[a,c],[b,a],[b,b],[b,c],[c,a],[c,b],[c,c]]
n 個の中から r 個を選ぶ組み合わせの数 nＣr を求める関数 comb_num(N, R) を定義してください。
> yaep02:comb_num(5, 3). 10 > yaep02:comb_num(10, 5). 252
リスト Xs から N 個の要素を選ぶ組み合わせを求める関数 combination(N, Xs) を定義してください。なお、生成した組み合わせはリストに格納して返すものとします。
> yaep02:combination(3, [a, b, c, d, e]). [[a,b,c], [a,b,d], [a,b,e], [a,c,d], [a,c,e], [a,d,e], [b,c,d], [b,c,e], [b,d,e], [c,d,e]]
リスト Xs から重複を許して N 個の要素を選ぶ組み合わせを求める関数 repeat_comb(N, Xs) を定義してください。なお、生成した組み合わせはリストに格納して返すものとします。
> yaep02:repeat_comb(3, [a, b, c, d]). [[a,a,a], [a,a,b], [a,a,c], [a,a,d], [a,b,b], [a,b,c], [a,b,d], [a,c,c], [a,c,d], [a,d,d], [b,b,b], [b,b,c], [b,b,d], [b,c,c], [b,c,d], [b,d,d], [c,c,c], [c,c,d], [c,d,d], [d,d,d]]
リストを N 番目の要素で二分割する関数 split_nth を定義してください。分割したリストはタプルに格納して返すものとします。
> yaep02:split_nth(3, [a, b, c, d, e, f]).
{[a,b],[c,d,e,f]}
> yaep02:split_nth(4, [a, b, c, d, e, f]).
{[a,b,c],[d,e,f]}
> yaep02:split_nth(1, [a, b, c, d, e, f]).
{[],[a,b,c,d,e,f]}
> yaep02:split_nth(6, [a, b, c, d, e, f]).
{[a,b,c,d,e],[f]}
> yaep02:split_nth(7, [a, b, c, d, e, f]).
{[a,b,c,d,e,f],[]}
リスト Xs を述語 Pred が真を返すものと偽を返すものの 2 つに分ける関数 partition(Pred, Xs) を定義してください。分割したリストはタプルに格納して返すものとします。
> yaep02:partition(fun(X) -> X rem 2 =:= 0 end, [1, 2, 3, 4, 5, 6, 7, 8]).
{[2,4,6,8],[1,3,5,7]}
> yaep02:partition1(fun(X) -> X rem 2 =:= 0 end, [1, 2, 3, 4, 5, 6, 7, 8]).
{[2,4,6,8],[1,3,5,7]}
> yaep02:partition2(fun(X) -> X rem 2 =:= 0 end, [1, 2, 3, 4, 5, 6, 7, 8]).
{[2,4,6,8],[1,3,5,7]}
リスト Xs の要素に述語 Pred を適用し、一つでも真を返す要素があれば真を返す関数 any(Pred, Xs) と、一つでも偽を返す要素があれば偽を返す (全てが真の場合に真を返す) 関数 every(Pred, Xs) を定義してください。
> yaep02:any(fun(X) -> X rem 2 =:= 0 end, [1, 3, 5, 7, 9]). false > yaep02:any(fun(X) -> X rem 2 =:= 0 end, [1, 3, 2, 5, 7, 9]). true > yaep02:every(fun(X) -> X rem 2 =:= 0 end, [2, 4, 6, 8, 10]). true > yaep02:every(fun(X) -> X rem 2 =:= 0 end, [2, 4, 6, 7, 8, 10]). false
Y と等しいリストの要素を全て X に置換する関数 substitute(X, Y, Xs) と、述語 Pred が真を返す要素を全て X に置換する関数 substitute_if(X, Pred, Xs) を定義してください。
> yaep02:substitute(a, b, [a, b, c, a, b, c, a, b, c]). [a,a,c,a,a,c,a,a,c] > yaep02:substitute_if(a, fun(X) -> X rem 2 =:= 0 end, [1, 2, 3, 4, 5, 6, 7, 8]). [1,a,3,a,5,a,7,a]
map(F, Xs) はリスト Xs の要素に関数 F を適用します。関数 maplist(F, Xs) は関数 F にリスト Xs そのものを渡します。ただし、繰り返すたびにリストの先頭要素は取り除かれていきます。関数 maplist を定義してください。
> yaep02:maplist(fun(X) -> X end, [1, 2, 3, 4, 5]). [[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5]] > yaep02:maplist(fun(X) -> yaep02:sum_list(X) end, [1, 2, 3, 4, 5]). [15,14,12,9,5]
リスト操作を一般化した関数 for_each_list(F, Comb, Term, Xs) を定義してください。ここで、F はリストの要素に適用する関数、Comb は関数の返り値を結合する関数、Term は終端の値、Xs がリストです。
> yaep02:for_each_list(fun(X) -> X end, fun(X,Y) -> X + Y end, 0, [1, 2, 3, 4, 5]). 15 > yaep02:for_each_list(fun(X) -> X * X end, fun(X,Y) -> X + Y end, 0, [1, 2, 3, 4, 5]). 55 > yaep02:for_each_list(fun(X) -> X end, fun lists:append/2, [], [[1, 2], [3], [4, 5]]). [1,2,3,4,5]
2 つのリスト Xs, Ys の要素 X, Y を取り出し、タプル {X, Y} にまとめてリストに格納して返す関数 zip(Xs, Ys) を定義してください。リストは短いほうに合わせるものとします。
> yaep02:zip([a, b, c, d, e], [1, 2, 3, 4, 5]).
[{a,1},{b,2},{c,3},{d,4},{e,5}]
リスト Xs の中で連続した等しい記号を部分リストにまとめる関数 pack を定義してください。
> yaep02:pack([a, a, a, b, b, c, d, d, d, d, e, e, e, e, e, e]). [[a,a,a],[b,b],[c],[d,d,d,d],[e,e,e,e,e,e]]
整列済みの整数を表すリスト Xs で、連続している部分列を {Start, End} に置き換える関数 pack_num_list(Xs) を定義してください。Start は部分列の始点、End は部分列の終点を表します。
> yaep02:pack_num_list([1, 2, 3, 5, 7, 8, 9, 10]).
[{1,3},{5,5},{7,10}]
なお、この問題は下記サイトを参考にさせていただきました。関係各位に感謝いたします。
問題 44 の逆変換を行う関数 expand_num_list を定義してください。
> yaep02:expand_num_list([{1, 3}, {5, 5}, {7, 10}]).
[1,2,3,5,7,8,9,10]
連続している同じ記号を {Code, Num} に変換する関数 encode を定義してください。Code は記号、num は個数を表します。このような変換を「ランレングス符号化」といいます。
> yaep02:encode([a, a, a, b, c, c, c, c, d, d, e, e, e]).
[{a,3},{b,1},{c,4},{d,2},{e,3}]
問題 46 の逆変換を行う関数 decode を定義してください。
> yaep02:decode([{a, 3}, {b, 1}, {c, 4}, {d, 2}, {e, 3}]).
[a,a,a,b,c,c,c,c,d,d,e,e,e]
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ A + B + C = N, A + E + I = N
├─┼─┼─┤ D + E + F = N, C + E + G = N
│Ｄ│Ｅ│Ｆ│ G + H + I = N
├─┼─┼─┤ A + D + G = N
│Ｇ│Ｈ│Ｉ│ B + E + H = N
└─┴─┴─┘ C + F + I = N
図 : 魔方陣
上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。縦横斜めの合計が等しくなるように数字を配置してください。
覆面算 SEND + MORE = MONEY を解くプログラムを作ってください。
S E N D
+ M O R E
-------------
M O N E Y
図 : 覆面算
計算式の数字を文字や記号に置き換えて、それを元の数字に戻すパズルを「覆面算」といいます。異なる文字は異なる数字を表し、同じ文字は同じ数字を表します。使用する数字は 0 から 9 までで、最上位の桁に 0 を入れることはできません。問題はデュードニーが 1924 年に発表したもので、覆面算の古典といわれる有名なパズルです。
自然数 n 以下の素数をすべて求める関数 sieve を作ってください。
> yaep02:sieve(100). [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
リスト : リストの生成 make_list(_, 0) -> []; make_list(X, N) when N > 0 -> [X | make_list(X, N - 1)]. tabulate(_, N, M) when N > M -> []; tabulate(F, N, M) -> [F(N) | tabulate(F, N + 1, M)]. % 別解 (末尾再帰) make_listi(_, 0, A) -> A; make_listi(X, N, A) -> make_listi(X, N - 1, [X | A]). make_listi(X, N) when N > 0 -> make_listi(X, N, []). tabulatei(F, N, N, A) -> [F(N) | A]; tabulatei(F, N, M, A) -> tabulatei(F, N, M - 1, [F(M) | A]). tabulatei(F, N, M) when N < M -> tabulatei(F, N, M, []).
make_list は簡単ですね。make_list を再帰呼び出しして N - 1 個の X を格納したリストを生成し、その先頭に X を追加します。tabulate も同じ考え方です。再帰呼び出しして N + 1 から M までのリストを生成し、その先頭に F(N) を追加します。
別解は末尾再帰でプログラムしたものです。どちらの場合も累積変数 A を使用します。make_listi は N 個の要素をリスト A に格納して返します。tabulatei は M, M - 1, M - 2, ..., N + 1, N までの整数値に関数 F を適用し、その結果をリスト A に格納して返します。
リスト : リストの要素を削除する remove(X, Xs) -> [Y || Y <- Xs, X =/= Y]. remove_if(Pred, Xs) -> [X || X <- Xs, not Pred(X)].
remove と remove_if はリスト内包表記を使うと簡単です。remove は引数 X と等しくない要素 Y をリストに格納します。remove_if は述語 Pred(Y) が偽となる要素をリストに格納します。
リスト : リストの平坦化 flatten([]) -> []; flatten([X | Xs]) -> flatten(X) ++ flatten(Xs); flatten(X) -> [X]. % 別解 (++ を使わないバージョン) flatten1([], A) -> A; flatten1([X | Xs], A) -> flatten1(X, flatten1(Xs, A)); flatten1(X, A) -> [X | A].
flatten は簡単です。最初の節は空リストを平坦化すると空リストになることを表しています。次の節で、リストの先頭要素 X を取り出して、flatten を再帰呼び出しします。その結果と flatten(Xs) の結果を演算子 ++ で結合すればいいわけです。引数がリストでない場合は最後の節が選択されます。なお、Erlang の lists モジュールには同等の機能を持つ関数 flatten/1 が用意されています。
別解は演算子 ++ を使わないバージョンです。累積変数 A のリストに要素を格納していきます。2 番目の節で、flatten1(Xs, A) が先に評価されるので、リストの後ろから順番に要素が格納されていくことに注意してください。
別解の実行例を示します。
> yaep02:flatten1([a, b, [c, d, [e | f], g], h], []). [a,b,c,d,e,f,g,h]
リスト : 複数のリストを連結する concat([]) -> []; concat([X | Xs]) -> X ++ concat(Xs).
concat はリストの要素 X を取り出して、X と concat(Xs) の返り値を演算子 ++ で連結していくだけです。
リスト : マッピングしてから平坦化する flatmap(_, []) -> []; flatmap(F, [X | Xs]) -> F(X) ++ flatmap(F, Xs).
flatmap はリストの要素 X に関数 F を適用するだけで、あとは concat と同じです。
リスト : 順列の生成
permutation(0, _) -> [[]];
permutation(N, Xs) when N > 0 ->
flatmap(fun(X) -> lists:map(fun(Y) -> [X | Y] end,
permutation(N - 1, lists:delete(X, Xs))) end,
Xs).
% 高階関数版
permutation(F, 0, _, A) -> F(lists:reverse(A));
permutation(F, N, Xs, A) ->
lists:foreach(fun(X) -> permutation(F, N - 1, lists:delete(X, Xs), [X | A]) end, Xs).
permutation(F, N, Xs) when N > 0 -> permutation(F, N, Xs, []).
関数 permutation は引数のリスト Xs から N 個を選ぶ順列を生成し、それをリストに格納して返します。最初の節が再帰の停止条件で、空リストを格納したリストを返します。このリストに対して要素を追加します。この処理は map を二重に使うと簡単に実現できます。このとき、関数 flatmap を使ってマッピングと平坦化を行っています。
あとは無名関数の中で permutation を再帰呼び出しをして、N - 1 個を選ぶ順列を生成します。そして、その返り値にリスト Xs の要素 X を追加すれば、N 個を選ぶ順列を生成することができます。
順列の総数が多い場合は、リストに格納して返すよりも高階関数版を使ったほうが便利でしょう。
リスト : 重複順列
repeat_perm(0, _) -> [[]];
repeat_perm(N, Xs) when N > 0 ->
flatmap(fun(X) -> lists:map(fun(Y) -> [X | Y] end,
repeat_perm(N - 1, Xs)) end,
Xs).
% 高階関数版
repeat_perm(F, 0, _, A) -> F(lists:reverse(A));
repeat_perm(F, N, Xs, A) ->
lists:foreach(fun(X) -> repeat_perm(F, N - 1, Xs, [X | A]) end, Xs).
repeat_perm(F, N, Xs) when N > 0 -> repeat_perm(F, N, Xs, []).
重複順列も簡単です。選んだ要素を取り除く必要がないので、repeat_perm を再帰呼び出しするとき、リスト Xs をそのまま渡すだけです。重複順列の総数が多い場合は、リストに格納して返すよりも高階関数版を使ったほうが便利でしょう。
組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。この公式をそのままプログラムすることもできますが、次の式を使うともっと簡単にプログラムできます。
この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは再帰定義を使って簡単にプログラムできます。
リスト : 組み合わせの数 comb_num(_, 0) -> 1; comb_num(N, N) -> 1; comb_num(N, R) -> comb_num(N, R - 1) * (N - R + 1) div R.
組み合わせの生成は、次に示す組み合わせの公式と同じ考え方でプログラムすることができます。
プログラムは次のようになります。
リスト : 組み合わせの生成 combination(0, _) -> [[]]; combination(N, Xs) when length(Xs) =:= N -> [Xs]; combination(N, [Y | Ys]) -> lists:map(fun(X) -> [Y | X] end, combination(N - 1, Ys)) ++ combination(N, Ys). % 高階関数版 combination(F, 0, _, A) -> F(lists:reverse(A)); combination(F, N, Xs, A) when length(Xs) =:= N -> F(lists:reverse(A) ++ Xs); combination(F, N, [X | Xs], A) -> combination(F, N - 1, Xs, [X | A]), combination(F, N, Xs, A). combination(F, N, Xs) -> combination(F, N, Xs, []).
最初の節は個数 N が 0 の場合です。選択する要素がないので空リストを格納したリストを返します。次の節で、N と Xs の要素数が同じ場合は、その要素を全て選択するのでリスト [Xs] を返します。そうでなければ、先頭要素 Y を選びます。残りのリスト Ys から N - 1 個を選ぶ組み合わせを生成して、その先頭に Y を追加します。あとは、Ys から N 個を選ぶ組み合わせを combination で求めて、演算子 ++ で連結するだけです。
組み合わせの数が多くなる場合は高階関数版を使うと便利でしょう。
リスト : 重複組み合わせ
repeat_comb(0, _) -> [[]];
repeat_comb(N, [X]) -> [make_list(X, N)];
repeat_comb(N, [Y | Ys]) ->
lists:map(fun(X) -> [Y | X] end,
repeat_comb(N - 1, [Y | Ys])) ++ repeat_comb(N, Ys).
% 高階関数版
repeat_comb(F, 0, _, A) -> F(lists:reverse(A));
repeat_comb(F, N, [X], A) -> F(lists:reverse(A) ++ make_list(X, N));
repeat_comb(F, N, [X | Xs], A) ->
repeat_comb(F, N - 1, [X | Xs], [X | A]), repeat_comb(F, N, Xs, A).
repeat_comb(F, N, Xs) -> repeat_comb(F, N, Xs, []).
重複組み合わせを求める repeat_comb も簡単です。2 番目の節で、リストに要素が一つしかない場合は、その要素 X を N 個選びます。make_list で X を N 個格納したリストを生成します。最後の節では、先頭要素 Y を選んだあと、それを取り除かないで N - 1 個の要素を選びます。組み合わせの数が多くなる場合は高階関数版を使うと便利でしょう。
リスト : n 番目の要素で分割する
split_nth(N, Xs) when N > 0 -> {take(N - 1, Xs), drop(N - 1, Xs)}.
split_nth は take と drop を使うと簡単です。take で先頭から N - 1 個の要素を取り出し、drop で先頭から N - 1 個の要素を取り除くだけです。
リスト : リストの分割
partition(_, []) -> {[], []};
partition(Pred, [X | Xs]) ->
{A, B} = partition(Pred, Xs),
case Pred(X) of
true -> {[X | A], B};
false -> {A, [X | B]}
end.
% 別解
partition1(Pred, Xs) -> {[X || X <- Xs, Pred(X)], [X || X <- Xs, not Pred(X)]}.
partition2(Pred, Xs) ->
Ys = [X || X <- Xs, Pred(X)], {Ys, difference(Xs, Ys)}.
最初の節で、リストが空リストならば、空リストを 2 つ格納したタプルを返します。次の節で、partition を再帰呼び出しして、その返り値と {A, B} をマッチングさせます。そして、Pred(X) が真ならば X を A に追加し、そうでなければ B に追加します。別解はリスト内包表記を使ってプログラムしたものです。
リスト : any と every
any(_, []) -> false;
any(Pred, [X | Xs]) ->
case Pred(X) of
true -> true;
false -> any(Pred, Xs)
end.
every(_, []) -> true;
every(Pred, [X | Xs]) ->
case Pred(X) of
true -> every(Pred, Xs);
false -> false
end.
any と every は簡単です。リストを X と Xs に分解して、Pred(X) が真を返す場合、any は true を返します。逆に偽を返す場合、every は false を返します。それ以外の場合は再帰呼び出しして次の要素をチェックします。引数のリストが空リストになった場合、any は false を返し、every は true を返します。
なお、Erlang のモジュール lists には同等の働きをする関数 any と all があります。
リスト : リストの置換
substitute(_, _, []) -> [];
substitute(X, Y, [Y | Ys]) -> [X | substitute(X, Y, Ys)];
substitute(X, Y, [Z | Zs]) -> [Z | substitute(X, Y, Zs)].
substitute_if(_, _, []) -> [];
substitute_if(X, Pred, [Y | Ys]) ->
case Pred(Y) of
true -> [X | substitute_if(X, Pred, Ys)];
false -> [Y | substitute_if(X, Pred, Ys)]
end.
substitute はリストの要素が引数 Y と等しい場合、その要素を引数 X に置き換えます。substitute_if は Pred(Y) が真を返す場合、その要素を引数 X に置き換えます。そうでなければ、要素 Y をそのままリストに追加します。
リスト : maplist maplist(_, []) -> []; maplist(F, Xs) -> [F(Xs) | maplist(F, tl(Xs))].
maplist は簡単です。関数 F に引数のリスト Xs をそのまま渡すだけです。maplist を再帰呼び出しするときは、先頭の要素を取り除いたリスト tl(Xs) を渡します。
maplist を使うと map は次のように定義することができます。
リスト : map の定義 map(F, Xs) -> maplist(fun(X) -> F(hd(X)) end, Xs).
リスト : リスト操作の一般化
for_each_list(_, _, Term, []) -> Term;
for_each_list(F, Comb, Term, [X | Xs]) ->
Comb(F(X), for_each_list(F, Comb, Term, Xs)).
関数 for_each_list の引数 F はリストの要素に適用する関数、Comb は F の返り値と for_each_list の返り値を結合する関数、Term はリストの終端で返す値です。プログラムは簡単で、引数のリストが空リストならば Term を返します。そうでなければ、リストの要素 X に関数 F を適用し、その返り値と for_each_list の返り値を関数 Comb で結合します。
リスト : zip
zip([], _) -> [];
zip(_, []) -> [];
zip([X | Xs], [Y | Ys]) -> [{X, Y} | zip(Xs, Ys)].
zip はリストの要素 X, Y を取り出してタプルにまとめ、それをリスト追加していくだけです。
リスト : 連続した同じ記号を部分リストにまとめる pack([], Ys, A) -> lists:reverse([Ys | A]); pack([X | Xs], [X | Ys], A) -> pack(Xs, [X, X | Ys], A); pack([X | Xs], Ys, A) -> pack(Xs, [X], [Ys | A]). pack([X | Xs]) -> pack(Xs, [X], []).
引数 Ys と A は累積変数です。Ys は連続した記号を格納するリストで、そのリストを A に格納します。最初の節で、引数のリストが空リストの場合は Ys を A に格納し、そのリストを reverse で反転して返します。
次の節で、リストの先頭要素 X が Ys の先頭要素と等しい場合は X を Ys に追加します。そうでない場合は最後の節で Ys を A に追加します。第 2 引数のリストに [X] を渡して pack を再帰呼び出しします。あとは pack/1 から pack/3 を呼び出すだけです。
リスト : 連続している数列を (s, e) で表す
pack_num_list([], A) -> lists:reverse(A);
pack_num_list([X | Xs], [{S, E} | Ys]) when X =:= E + 1 ->
pack_num_list(Xs, [{S, X} | Ys]);
pack_num_list([X | Xs], Ys) -> pack_num_list(Xs, [{X, X} | Ys]).
pack_num_list([X | Xs]) -> pack_num_list(Xs, [{X, X}]).
pack_num_list/2 は引数 A を累積変数として使います。最初の節で第 1 引数が空リストの場合は A を反転して返します。次の節で、リストを X と Xs に分解し、A の先頭要素を {S, E} で取り出します。X = E + 1 ならば X は連続した数字です。リスト A の {S, E} を {S, X} に置き換えます。そうでなければ X は連続していないので、最後の節でリスト A に {X, X} を追加します。あとは pack_num_list/2 を再帰呼び出しして次の数字を調べます。
リスト : {S, E} を数列に戻す
expand_num_list([]) -> [];
expand_num_list([{S, E} | Xs]) -> iota(S, E) ++ expand_num_list(Xs).
expand_num_list は iota を使うと簡単です。最初の節が再帰の停止条件です。次の節で、{S, E} を iota で数列に変換します。expand_num_list を再帰呼び出しして残りのリスト Xs を数列に戻し、その返り値に iota で変換したリストを演算子 ++ で連結します。
リスト : ランレングス符号化
encode(Ys) -> [{X, length(Xs) + 1} || [X | Xs] <- pack(Ys)].
encode はリスト内包表記を使うと簡単です。最初に pack で連続している記号をリストにまとめます。そして、生成器で要素を取り出し、X と Xs に分解します。あとは、要素 X とリストの長さ length(Xs) + 1 をタプルに格納するだけです。
リスト : ランレングス復号
decode([]) -> [];
decode([{X, L} | Xs]) -> make_list(X, L) ++ decode(Xs).
関数 decode は make_list を使うと簡単です。{X, L} を make_list でリストに展開して、その結果と decode(Xs) の返り値を演算子 ++ で連結するだけです。
リスト : 魔方陣
check1([A,B,C,D,E,F,G,H,I]) ->
N = A + B + C,
D + E + F =:= N andalso
G + H + I =:= N andalso
A + D + G =:= N andalso
B + E + H =:= N andalso
C + F + I =:= N andalso
A + E + I =:= N andalso
C + E + G =:= N.
magic1() -> permutation(fun(X) -> case check1(X) of
true -> io:write(X), io:nl();
false -> false
end
end,
9,
iota(1, 9)).
単純な生成検定法です。実行結果は次のようになります。
> yaep02:magic1(). [8,3,4,1,5,9,6,7,2] [8,1,6,3,5,7,4,9,2] [6,7,2,1,5,9,8,3,4] [6,1,8,7,5,3,2,9,4] [4,9,2,3,5,7,8,1,6] [4,3,8,9,5,1,2,7,6] [2,9,4,7,5,3,6,1,8] [2,7,6,9,5,1,4,3,8] ok
解は 8 通り出力されましたが、重複解を取り除くと解は一通りしかありません。重複解のチェックは面倒だと思われる方もいるでしょう。ところが、下図のように四隅の大小関係を利用すると簡単です。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│
├─┼─┼─┤ A < C < G
│Ｄ│Ｅ│Ｆ│
├─┼─┼─┤ A < I
│Ｇ│Ｈ│Ｉ│
└─┴─┴─┘
図 : 対称解のチェック
魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。また、順列を生成するとき、重複解のチェックを入れると枝刈りと同じ効果を得ることができます。興味のある方は試してみてください。
式 SEND + MORE = MONEY は足し算なので、M が 1 であることはすぐにわかります。ここでは、それ以外の数字を求めるプログラムを作ります。単純な生成検定法でプログラムを作ると、次のようになります。
リスト：覆面算
check2([S, E, N, D, O, R, Y]) ->
N1 = S * 1000 + E * 100 + N * 10 + D,
N2 = 1000 + O * 100 + R * 10 + E,
N3 = 10000 + O * 1000 + N * 100 + E * 10 + Y,
if
N1 + N2 =:= N3 -> io:format('~w + ~w = ~w~n', [N1, N2, N3]);
true -> false
end.
solve2() -> permutation(fun(X) -> check2(X) end, 7, [0,2,3,4,5,6,7,8,9]).
1 を除いた 9 個の数字の中から 7 個の数字を選ぶ順列を permutation で生成し、関数 check2 で式 SEND + MORE = MONEY を満たしているかチェックします。とても簡単なプログラムですね。さっそく実行してみましょう。
> yaep02:solve2(). 9567 + 1085 = 10652 ok
答えは 9567 + 1085 = 10652 の 1 通りしかありません。
素数を求める基本的な考え方は簡単です。最初に、2 から n までの整数列を生成します。先頭の 2 は素数なので、この整数列から 2 で割り切れる整数を取り除き除きます。2 で割り切れる整数が取り除かれたので、残った要素の先頭が素数になります。先頭要素は 3 になるので、今度は 3 で割り切れる整数を取り除けばいいのです。このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩 (ふるい) 」といいます。
プログラムは次のようになります。
リスト : 素数 (エラトステネスの篩)
sieve([], A) -> lists:reverse(A);
sieve([X | Xs], A) ->
sieve(remove_if(fun(Y) -> Y rem X =:= 0 end, Xs), [X | A]).
sieve(N) -> sieve(iota(2, N), []).
sieve/2 の引数 A は素数を格納するリストです。iota で 2 から N までの整数列を生成し、それを sieve/2 に渡します。sieve/2 はリストの先頭要素 X で割り切れる要素を remove_if で取り除き、sieve/2 を再帰呼び出しします。このとき、累積変数 A に素数 X を追加します。第 1 引数が空リストになった場合、累積変数には素数が逆順にセットされているので、reverse で反転して返します。
sieve には無駄な処理があります。リストの先頭要素 x が √n よりも大きい場合、リストには素数しか残っていません。つまり、ふるいにかけるのは x <= √n まででいいのです。これをプログラムすると次のようになります。
リスト : 別解
revAppend([], Ys) -> Ys;
revAppend([X | Xs], Ys) -> revAppend(Xs, [X | Ys]).
sieve1(_, [], A) -> lists:reverse(A);
sieve1(N, [X | Xs], A) ->
if
N < X * X -> revAppend(A, [X | Xs]);
true -> sieve1(N, remove_if(fun(Y) -> Y rem X =:= 0 end, Xs), [X | A])
end.
sieve1(N) -> sieve1(N, iota(2, N), []).
sieve1 の 2 番目の節で、リストの先頭要素 X が X * X > N ならば、累積変数 A とリスト [X | Xs] を revAppend で連結して返します。revAppend は第 1 引数のリストを反転して第 2 引数のリストと連結します。これで sieve よりも速く素数を求めることができます。
%
% yaep02.erl : Yet Another Erlang Problems (2)
%
% Copyright (C) 2011-2024 Makoto Hiroi
%
-module(yaep02).
-export([make_list/2, tabulate/3, make_listi/2, tabulatei/3, remove/2, remove_if/2]).
-export([flatten/1, flatten1/2, concat/1, flatmap/2, permutation/2, permutation/3]).
-export([repeat_perm/2, repeat_perm/3, comb_num/2, combination/2, combination/3]).
-export([repeat_comb/2, repeat_comb/3, split_nth/2, partition/2, partition1/2, partition2/2]).
-export([any/2, every/2, substitute/3, substitute_if/3, maplist/2, for_each_list/4]).
-export([zip/2, pack/1, pack_num_list/1, expand_num_list/1, encode/1, decode/1, magic1/0]).
-export([solve2/0, sieve/1, sieve1/1]).
-import(yaep01, [take/2, drop/2, difference/2, iota/2]).
make_list(_, 0) -> [];
make_list(X, N) when N > 0 -> [X | make_list(X, N - 1)].
tabulate(_, N, M) when N > M -> [];
tabulate(F, N, M) -> [F(N) | tabulate(F, N + 1, M)].
% 別解 (末尾再帰)
make_listi(_, 0, A) -> A;
make_listi(X, N, A) -> make_listi(X, N - 1, [X | A]).
make_listi(X, N) when N > 0 -> make_listi(X, N, []).
tabulatei(F, N, N, A) -> [F(N) | A];
tabulatei(F, N, M, A) -> tabulatei(F, N, M - 1, [F(M) | A]).
tabulatei(F, N, M) when N < M -> tabulatei(F, N, M, []).
remove(X, Xs) -> [Y || Y <- Xs, X =/= Y].
remove_if(Pred, Xs) -> [X || X <- Xs, not Pred(X)].
flatten([]) -> [];
flatten([X | Xs]) -> flatten(X) ++ flatten(Xs);
flatten(X) -> [X].
% 別解 (++ を使わないバージョン)
flatten1([], A) -> A;
flatten1([X | Xs], A) -> flatten1(X, flatten1(Xs, A));
flatten1(X, A) -> [X | A].
concat([]) -> [];
concat([X | Xs]) -> X ++ concat(Xs).
flatmap(_, []) -> [];
flatmap(F, [X | Xs]) -> F(X) ++ flatmap(F, Xs).
permutation(0, _) -> [[]];
permutation(N, Xs) when N > 0 ->
flatmap(fun(X) -> lists:map(fun(Y) -> [X | Y] end,
permutation(N - 1, lists:delete(X, Xs))) end,
Xs).
% 高階関数版
permutation(F, 0, _, A) -> F(lists:reverse(A));
permutation(F, N, Xs, A) ->
lists:foreach(fun(X) -> permutation(F, N - 1, lists:delete(X, Xs), [X | A]) end, Xs).
permutation(F, N, Xs) when N > 0 -> permutation(F, N, Xs, []).
repeat_perm(0, _) -> [[]];
repeat_perm(N, Xs) when N > 0 ->
flatmap(fun(X) -> lists:map(fun(Y) -> [X | Y] end,
repeat_perm(N - 1, Xs)) end,
Xs).
% 高階関数版
repeat_perm(F, 0, _, A) -> F(lists:reverse(A));
repeat_perm(F, N, Xs, A) ->
lists:foreach(fun(X) -> repeat_perm(F, N - 1, Xs, [X | A]) end, Xs).
repeat_perm(F, N, Xs) when N > 0 -> repeat_perm(F, N, Xs, []).
comb_num(_, 0) -> 1;
comb_num(N, N) -> 1;
comb_num(N, R) -> comb_num(N, R - 1) * (N - R + 1) div R.
combination(0, _) -> [[]];
combination(N, Xs) when length(Xs) =:= N -> [Xs];
combination(N, [Y | Ys]) ->
lists:map(fun(X) -> [Y | X] end, combination(N - 1, Ys)) ++ combination(N, Ys).
% 高階関数版
combination(F, 0, _, A) -> F(lists:reverse(A));
combination(F, N, Xs, A) when length(Xs) =:= N -> F(lists:reverse(A) ++ Xs);
combination(F, N, [X | Xs], A) ->
combination(F, N - 1, Xs, [X | A]), combination(F, N, Xs, A).
combination(F, N, Xs) -> combination(F, N, Xs, []).
repeat_comb(0, _) -> [[]];
repeat_comb(N, [X]) -> [make_list(X, N)];
repeat_comb(N, [Y | Ys]) ->
lists:map(fun(X) -> [Y | X] end,
repeat_comb(N - 1, [Y | Ys])) ++ repeat_comb(N, Ys).
% 高階関数版
repeat_comb(F, 0, _, A) -> F(lists:reverse(A));
repeat_comb(F, N, [X], A) -> F(lists:reverse(A) ++ make_list(X, N));
repeat_comb(F, N, [X | Xs], A) ->
repeat_comb(F, N - 1, [X | Xs], [X | A]), repeat_comb(F, N, Xs, A).
repeat_comb(F, N, Xs) -> repeat_comb(F, N, Xs, []).
split_nth(N, Xs) when N > 0 -> {take(N - 1, Xs), drop(N - 1, Xs)}.
partition(_, []) -> {[], []};
partition(Pred, [X | Xs]) ->
{A, B} = partition(Pred, Xs),
case Pred(X) of
true -> {[X | A], B};
false -> {A, [X | B]}
end.
% 別解
partition1(Pred, Xs) -> {[X || X <- Xs, Pred(X)], [X || X <- Xs, not Pred(X)]}.
partition2(Pred, Xs) ->
Ys = [X || X <- Xs, Pred(X)], {Ys, difference(Xs, Ys)}.
any(_, []) -> false;
any(Pred, [X | Xs]) ->
case Pred(X) of
true -> true;
false -> any(Pred, Xs)
end.
every(_, []) -> true;
every(Pred, [X | Xs]) ->
case Pred(X) of
true -> every(Pred, Xs);
false -> false
end.
substitute(_, _, []) -> [];
substitute(X, Y, [Y | Ys]) -> [X | substitute(X, Y, Ys)];
substitute(X, Y, [Z | Zs]) -> [Z | substitute(X, Y, Zs)].
substitute_if(_, _, []) -> [];
substitute_if(X, Pred, [Y | Ys]) ->
case Pred(Y) of
true -> [X | substitute_if(X, Pred, Ys)];
false -> [Y | substitute_if(X, Pred, Ys)]
end.
maplist(_, []) -> [];
maplist(F, Xs) -> [F(Xs) | maplist(F, tl(Xs))].
for_each_list(_, _, Term, []) -> Term;
for_each_list(F, Comb, Term, [X | Xs]) ->
Comb(F(X), for_each_list(F, Comb, Term, Xs)).
zip([], _) -> [];
zip(_, []) -> [];
zip([X | Xs], [Y | Ys]) -> [{X, Y} | zip(Xs, Ys)].
pack([], Ys, A) -> lists:reverse([Ys | A]);
pack([X | Xs], [X | Ys], A) -> pack(Xs, [X, X | Ys], A);
pack([X | Xs], Ys, A) -> pack(Xs, [X], [Ys | A]).
pack([X | Xs]) -> pack(Xs, [X], []).
pack_num_list([], A) -> lists:reverse(A);
pack_num_list([X | Xs], [{S, E} | Ys]) when X =:= E + 1 ->
pack_num_list(Xs, [{S, X} | Ys]);
pack_num_list([X | Xs], Ys) -> pack_num_list(Xs, [{X, X} | Ys]).
pack_num_list([X | Xs]) -> pack_num_list(Xs, [{X, X}]).
expand_num_list([]) -> [];
expand_num_list([{S, E} | Xs]) -> iota(S, E) ++ expand_num_list(Xs).
encode(Ys) -> [{X, length(Xs) + 1} || [X | Xs] <- pack(Ys)].
decode([]) -> [];
decode([{X, L} | Xs]) -> make_list(X, L) ++ decode(Xs).
check1([A,B,C,D,E,F,G,H,I]) ->
N = A + B + C,
D + E + F =:= N andalso
G + H + I =:= N andalso
A + D + G =:= N andalso
B + E + H =:= N andalso
C + F + I =:= N andalso
A + E + I =:= N andalso
C + E + G =:= N.
magic1() -> permutation(fun(X) -> case check1(X) of
true -> io:write(X), io:nl();
false -> false
end
end,
9,
iota(1, 9)).
check2([S, E, N, D, O, R, Y]) ->
N1 = S * 1000 + E * 100 + N * 10 + D,
N2 = 1000 + O * 100 + R * 10 + E,
N3 = 10000 + O * 1000 + N * 100 + E * 10 + Y,
if
N1 + N2 =:= N3 -> io:format('~w + ~w = ~w~n', [N1, N2, N3]);
true -> false
end.
solve2() -> permutation(fun(X) -> check2(X) end, 7, [0,2,3,4,5,6,7,8,9]).
sieve([], A) -> lists:reverse(A);
sieve([X | Xs], A) ->
sieve(remove_if(fun(Y) -> Y rem X =:= 0 end, Xs), [X | A]).
sieve(N) -> sieve(iota(2, N), []).
revAppend([], Ys) -> Ys;
revAppend([X | Xs], Ys) -> revAppend(Xs, [X | Ys]).
sieve1(_, [], A) -> lists:reverse(A);
sieve1(N, [X | Xs], A) ->
if
N < X * X -> revAppend(A, [X | Xs]);
true -> sieve1(N, remove_if(fun(Y) -> Y rem X =:= 0 end, Xs), [X | A])
end.
sieve1(N) -> sieve1(N, iota(2, N), []).