M.Hiroi's Home Page

Erlang Programming

Yet Another Erlang Problems

[ PrevPage | Erlang | NextPage ]

●問題66

自然数 N を素因数分解する関数 factorization(N) を定義してください。返り値はリスト [{P, Q}, ...] で、{P . Q} は PQ を表します。

> yaep:factorization(6).
[{2,1},{3,1}]
> yaep:factorization(12345678).
[{2,1},{3,2},{47,1},{14593,1}]
> yaep:factorization(123456789).
[{3,2},{3607,1},{3803,1}]
> yaep:factorization(1234567890).
[{2,1},{3,2},{5,1},{3607,1},{3803,1}]
> yaep:factorization(1111111111).
[{11,1},{41,1},{271,1},{9091,1}]

解答66

●問題67

自然数 N の約数の個数を求める関数 divisor_num(N) を定義してください。

> yaep:divisor_num(6).
4
> yaep:divisor_num(12345678).
24
> yaep:divisor_num(123456789).
12
> yaep:divisor_num(1234567890).
48
> yaep:divisor_num(1111111111).
16

解答67

●問題68

自然数 N の約数の合計値を求める関数 divisor_sum(N) を定義してください。

> yaep:divisor_sum(6).
12
> yaep:divisor_sum(12345678).
27319968
> yaep:divisor_sum(123456789).
178422816
> yaep:divisor_sum(1234567890).
3211610688
> yaep:divisor_sum(1111111111).
1246404096

解答68

●問題69

自然数 N の約数をリストに格納して返す関数 divisor(N) を定義してください。

> yaep:divisor(6).
[1,2,3,6]
> yaep:divisor(12345678).
[1,2,3,6,9,18,47,94,141,282,423,846,14593,29186,43779,87558,
 131337,262674,685871,1371742,2057613,4115226,6172839,
 12345678]
> yaep:divisor(123456789).
[1,3,9,3607,3803,10821,11409,32463,34227,13717421,41152263,
 123456789]
> yaep:divisor(1234567890).
[1,2,3,5,6,9,10,15,18,30,45,90,3607,3803,7214,7606,10821,
 11409,18035,19015,21642,22818,32463,34227,36070,38030,54105,
 57045,64926|...]
> yaep:divisor(1111111111).
[1,11,41,271,451,2981,9091,11111,100001,122221,372731,
 2463661,4100041,27100271,101010101,1111111111]

解答69

●問題70

完全数 - Wikipedia によると、『完全数(かんぜんすう,perfect number)とは、その数自身を除く約数の和が、その数自身と等しい自然数のことである。』 とのことです。自然数 N 以下の完全数を求める関数 perfect_number(N) を定義してください。

> yaep:perfect_number(10000).
6
28
496
8128
ok

解答70

●問題71

友愛数 - Wikipedia によると、『友愛数(ゆうあいすう)とは、異なる2つの自然数の組で、自分自身を除いた約数の和が、互いに他方と等しくなるような数をいう。』 とのことです。自然数 N 以下の友愛数を求める関数 yuuai_number(N) を定義してください。

> yaep:yuuai_number(100000).
{220,284}
{1184,1210}
{2620,2924}
{5020,5564}
{6232,6368}
{10744,10856}
{12285,14595}
{17296,18416}
{63020,76084}
{66928,66992}
{67095,71145}
{69615,87633}
{79750,88730}
ok

解答71

●問題72

整数 N を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。簡単な例を示します。

n = 6
6 分割 : 1 + 1 + 1 + 1 + 1 + 1
5 分割 : 1 + 1 + 1 + 1 + 2
4 分割 : 1 + 1 + 1 + 3
         1 + 1 + 2 + 2
3 分割 : 1 + 1 + 4
         1 + 2 + 3
         2 + 2 + 2
2 分割 : 1 + 5
         2 + 4
         3 + 3
1 分割 : 6

6 の場合、分割の仕方は 11 通りあります。この数を「分割数」といいます。自然数 N の分割数を求める関数 partition_number を定義してください。

> lists:foreach(fun(X) -> io:write(yaep:part_num(X)), io:nl() end, yaep:iota(1, 20)).
1
2
3
5
7
11
15
22
30
42
56
77
101
135
176
231
297
385
490
627
ok

解答72

●問題73

整数 N の分割の仕方をすべて求める高階関数 partition_of_integer(F, N) を定義してください。

> yaep:partition_of_integer(fun io:write/1, 5).
[5][4,1][3,2][3,1,1][2,2,1][2,1,1,1][1,1,1,1,1]ok
> yaep:partition_of_integer(fun io:write/1, 6).
[6][5,1][4,2][4,1,1][3,3][3,2,1][3,1,1,1][2,2,2][2,2,1,1][2,1,1,1,1][1,1,1,1,1,1]ok
> yaep:partition_of_integer(fun io:write/1, 7).
[7][6,1][5,2][5,1,1][4,3][4,2,1][4,1,1,1][3,3,1][3,2,2][3,2,1,1][3,1,1,1,1]
[2,2,2,1][2,2,1,1,1][2,1,1,1,1,1][1,1,1,1,1,1,1]ok

解答73

●問題74

M 個の整数 1, 2, ..., M の順列を考えます。このとき、i 番目の要素が整数 i ではない順列を「完全順列」といいます。1 から M までの整数値で完全順列を生成する高階関数 perfect_permutation(F, M) を定義してください。

> yaep:perfect_permutation(fun io:write/1, 3).
[2,3,1][3,1,2]ok
> yaep:perfect_permutation(fun io:write/1, 4).
[2,1,4,3][2,3,4,1][2,4,1,3][3,1,4,2][3,4,1,2][3,4,2,1][4,1,2,3][4,3,1,2][4,3,2,1]ok

解答74

●問題75

完全順列の総数を「モンモール数 (Montmort number) 」といいます。モンモール数は次の漸化式で求めることができます。

A1 = 0
A2 = 1
An = (n - 1) * (An-1 + An-2)  ; n >= 3

モンモール数を求める関数 montmort_number を定義してください。

> yaep:montmort_number(1).
0
> yaep:montmort_number(2).
1
> yaep:montmort_number(3).
2
> yaep:montmort_number(4).
9
> yaep:montmort_number(5).
44
> yaep:montmort_number(10).
1334961
> yaep:montmort_number(20).
895014631192902121
> yaep:montmort_number(30).
97581073836835777732377428235481

解答75

●問題76

リストで表した集合 Xs を分割することを考えます。たとえば、集合 [1, 2, 3] は次のように分割することができます。

1 分割 : [[1, 2, 3]]
2 分割 : [[1, 2]. [3]], [[1, 3] [2]], [[1], [2, 3]]
3 分割 ; [[1], [2], [3]]

このように、分割した集合 Ys は元の集合 Xs の部分集合になります。分割した部分集合の積は空集合になり、分割した部分集合のすべての和を求めると元の集合になります。

Xs の分割の仕方をすべて求める高階関数 parititon_of_set(F, Xs) を定義してください。

> yaep:partition_of_set(fun(X) -> io:write(X), io:nl() end, [1,2,3]).
[[1,2,3]]
[[1],[2,3]]
[[1,2],[3]]
[[1,3],[2]]
[[1],[2],[3]]
ok
> yaep:partition_of_set(fun(X) -> io:write(X), io:nl() end, [1,2,3,4]).
[[1,2,3,4]]
[[1],[2,3,4]]
[[1,2],[3,4]]
[[1,3,4],[2]]
[[1],[2],[3,4]]
[[1,2,3],[4]]
[[1,4],[2,3]]
[[1],[2,3],[4]]
[[1,2,4],[3]]
[[1,3],[2,4]]
[[1],[2,4],[3]]
[[1,2],[3],[4]]
[[1,3],[2],[4]]
[[1,4],[2],[3]]
[[1],[2],[3],[4]]
ok

解答76

●問題77

集合を分割する方法の総数を「ベル数 (Bell Number) 」といい、次の漸化式で求めることができます。

B(0) = 1
          n
B(n+1) =  Σ nk * B(k)    ; n >= 1
          k=0

ベル数を求める関数 bell_number(N) を定義してください。

> yaep:bell_number(0).
1
> yaep:bell_number(1).
1
> yaep:bell_number(2).
2
> yaep:bell_number(3).
5
> yaep:bell_number(4).
15
> yaep:bell_number(5).
52
> yaep:bell_number(10).
115975
> yaep:bell_number(20).
51724158235372
> yaep:bell_number(30).
846749014511809332450147
> yaep:bell_number(40).
157450588391204931289324344702531067
> yaep:bell_number(50).
185724268771078270438257767181908917499221852770

解答77

●問題78

K 個の要素をもつ集合 Xs を要素数が等しい M 個の部分集合に分割することを考えます。部分集合の要素数 N は K / M になります。分割の仕方をすべて求める高階関数 group_partition(F, N, M, Xs) を定義してください。

> yaep:group_partition(fun(X) -> io:write(X), io:nl() end, 2, 2, [1,2,3,4]).
[[1,2],[3,4]]
[[1,4],[2,3]]
[[1,3],[2,4]]
ok
> yaep:group_partition(fun(X) -> io:write(X), io:nl() end, 2, 3, [1,2,3,4,5,6]).
[[1,2],[3,4],[5,6]]
[[1,4],[2,3],[5,6]]
[[1,3],[2,4],[5,6]]
[[1,2],[3,6],[4,5]]
[[1,6],[2,3],[4,5]]
[[1,3],[2,6],[4,5]]
[[1,2],[3,5],[4,6]]
[[1,5],[2,3],[4,6]]
[[1,3],[2,5],[4,6]]
[[1,6],[2,5],[3,4]]
[[1,5],[2,6],[3,4]]
[[1,6],[2,4],[3,5]]
[[1,4],[2,6],[3,5]]
[[1,5],[2,4],[3,6]]
[[1,4],[2,5],[3,6]]
ok

解答78

●問題79

集合を group_partition で分割するとき、その仕方の総数を求める関数 group_partition_number(N, M) を定義してください。引数 N は部分集合の要素数、M は部分集合の個数です。

> yaep:group_partition_number(2, 2).
3
> yaep:group_partition_number(2, 3).
15
> yaep:group_partition_number(3, 3).
280
> yaep:group_partition_number(3, 4).
15400
> yaep:group_partition_number(3, 5).
1401400

解答79

●問題80

中置記法で書かれた数式を計算するプログラムを作ってください。演算子は +, -, *, - で、カッコを使用することができます。数式はリストで表すことにします。

> yaep:expression([1, '+', 2, '+', 3, '+', 4]).
10
> yaep:expression([1, '+', 2, '-', 3, '+', 4]).
4
> yaep:expression([1, '+', 2, '*', 3, '+', 4]).
11
> yaep:expression([[1, '+', 2], '*', [3, '+', 4]]).
21
> yaep:expression([[1, '+', 2], '/', [3, '+', 4]]).
0.42857142857142855
> yaep:expression([[1, '+', 2], '/', [3, '-', 4]]).
-3.0

●解答66

リスト : 素因数分解

factor_sub(N, M, C) when N rem M =/= 0 -> {N, C};
factor_sub(N, M, C) -> factor_sub(N div M, M, C + 1).

factor_loop(I, N, A) when N < I * I ->
  if
    N > 1 -> lists:reverse([{N, 1} | A]);
    true -> lists:reverse(A)
  end;
factor_loop(I, N, A) ->
  {M, C} = factor_sub(N, I, 0),
  I2 = I + 2,
  if
    C > 0 -> factor_loop(I2, M, [{I, C} | A]);
    true -> factor_loop(I2, N, A)
  end.

factorization(N) ->
  {M, C} = factor_sub(N, 2, 0),
  if
    C > 0 -> factor_loop(3, M, [{2, C}]);
    true  -> factor_loop(3, N, [])
  end.

素因数分解は素数 2, 3, 5, ... で順番に割り算していけばいいのですが、いちいち素数を求めるのは大変なので、2 と 3 以上の奇数列で割り算していきます。関数 factor_sub は N を M で割り算します。このとき、M で割り切れる回数を求めます。factor_sub は M で割った回数と商をタプルに格納して返します。

関数 factor_loop は奇数列を生成します。変数 I は 3 で初期化します。A は結果を格納するリストです。N が 1 になる、または √N < I になったら繰り返しを終了します。そうでなければ、factor_sub を呼び出して N を I で割り算します。奇数列には素数ではないものがありますが、その前に小さな素数で素因数分解されているので、N がその値で割り切れることはありません。あとは、2 で割り算してから factor_loop を呼び出すだけです。

●解答67

整数 N の素因数分解ができると、約数の個数を求めるのは簡単です。N = pa * qb * rc とすると、約数の個数は (a + 1) * (b + 1) * (c + 1) になります。たとえば、12 は 22 * 31 になるので、約数の個数は 3 * 2 = 6 になります。実際、12 の約数は 1, 2, 3, 4, 6, 12 の 6 個です。

プログラムは次のようになります。

リスト : 約数の個数

divisor_num(N) ->
  lists:foldl(fun ({_, X}, A) -> A * (X + 1) end, 1, factorization(N)).

divisor_num は lists:foldl を使って X + 1 を a に掛け算していくだけです。

●解答68

整数 N の素因数分解ができると、約数の合計値を求めるのは簡単です。N の素因数分解が pa だった場合、その約数の合計値は次の式で求めることができます。

σ(p, a) = pa + pa-1 + ... + p2 + p + 1

たとえば、8 の素因数分解は 23 になり、素数の合計値は 8 + 4 + 2 + 1 = 15 になります。

pa の約数の合計値を σ(p, a) で表すことにします。n = pa * qb * rc の場合、n の約数の合計値は σ(p, a) * σ(q, b) * σ(r, c) になります。たとえば、12 は 22 * 3 に素因数分解できますが、その合計値は (4 + 2 + 1) * (3 + 1) = 28 となります。12 の約数は 1, 2, 3, 4, 6, 12 なので、その合計値は確かに 28 になります。

プログラムは次のようになります。

リスト : 約数の合計値

% 整数の累乗
pow(_, 0) -> 1;
pow(X, Y) when Y > 0, Y rem 2 =:= 0 ->
    Z = pow(X, Y div 2),
    Z * Z;
pow(X, Y) when Y > 0 ->
    Z = pow(X, Y div 2),
    X * Z * Z.

prime_sum(_, 0, A) -> A + 1;
prime_sum(P, N, A) -> prime_sum(P, N - 1, A + pow(P, N)).

divisor_sum(N) ->
  lists:foldl(fun({P, M}, A) -> prime_sum(P, M, 0) * A end, 1, factorization(N)).

関数 prime_sub は σ(p, n) を計算します。あとは lists:foldl で prime_sub の返り値を累積変数 a に掛け算していくだけです。

●解答69

p が素数の場合、pa の約数は次のように簡単に求めることができます。

pa, pa-1, ... p2, p, 1

n の素因数分解が pa * qb だったとすると、その約数は次のようになります。

(pa, pa-1, ... p2, p, 1) * qb,
(pa, pa-1, ... p2, p, 1) * qb-1,
        .....
(pa, pa-1, ... p2, p, 1) * q2,
(pa, pa-1, ... p2, p, 1) * q,
(pa, pa-1, ... p2, p, 1) * 1

たとえば、12 の約数は 24 = (1, 2, 4) と 3 = (1, 3) から、(1, 2, 4) * 1 と (1, 2, 4) * 3 のすべての要素 (1, 2, 4, 3, 6, 12) になります。

プログラムは次のようになります。

リスト : 約数をすべて求める

% P ^ N の約数を求める
divisor_sub(_, 0, A) -> [1 | A];
divisor_sub(P, N, A) when N > 0 -> divisor_sub(P, N - 1, [pow(P, N) | A]).

divisor_product(Xs, Ys) -> [X * Y || X <- Xs, Y <- Ys].

divisor_sub1([], A) -> A;
divisor_sub1([{P, N} | Xs], A) ->
  divisor_sub1(Xs, divisor_product(A, divisor_sub(P, N, []))).

divisor(N) -> 
  insert_sort(fun(X, Y) -> X < Y end, divisor_sub1(factorization(N), [1])).

関数 divisor_sub は PN の約数をリストに格納して返します。関数 divisor_product は 2 つのリスト Xs, Ys の要素を掛け合わせた結果をリストに格納して返します。あとは divisor_sub1 で素因数分解した結果を順番に取り出し、{P, N} を divisor_sub でリストに変換して、それを divisor_product で累積変数 a のリストと掛け合わせていくだけです。

●解答70

リスト : 完全数

perfect_number(N, X) when N < X -> ok;
perfect_number(N, X) ->
  M = divisor_sum(X),
  if
    M - X =:= X -> io:write(X), io:nl();
    true -> false
  end,
  perfect_number(N, X + 1).
perfect_number(N) -> perfect_number(N, 2).

完全数を求める perfect_number は簡単です。X の約数の合計値 M を divisor_sub で求め、その値から X を引いた値が X と等しければ完全数です。io:write で X を表示します。

●解答71

リスト : 友愛数

yuuai_number(N, X) when N < X -> ok;
yuuai_number(N, X) ->
  M = divisor_sum(X) - X,
  if
    X < M -> M1 = divisor_sum(M),
             if
               X =:= M1 - M -> io:write({X, M}), io:nl();
               true -> false
             end;
    true -> false
  end,
  yuuai_number(N, X + 1).
yuuai_number(N) -> yuuai_number(N, 2).

友愛数を求める yuuai_number も簡単です。divisor_sum で X の約数の合計値を求め、その値から X を引いた値を変数 M にセットします。M の約数の合計値 M1 から M を引いた値が X と等しければ、X と M は友愛数です。io:write で {X, M} を表示します。同じ組を表示しないようにするため、X < M を条件に入れています。

●解答72

整数 n を k 以下で分割する総数を求める関数を p(n, k) で表します。参考文献 [1] によると、p(n, k) は次の式で表すことができるそうです。

p(n, 1) = 1
p(1, k) = 1
p(0, k) = 1
p(n, k) = p(n - 1, 1) + p(n - 2, 2) + ... + p(n - k, k)

r = 1 の場合は簡単ですね。n 個の 1 を選ぶ方法しかありません。同様に n = 1 の場合も、1 を選ぶ方法しかありません。なお、n = 0 の場合は 1 とします。

p(n, k) の場合、まず 1 を選ぶとすると、残りの n - 1 から 1 で分割する方法は p(n - 1, 1) 通りになります。2 を選ぶとすると、残りの n - 2 から 2 以下で分割する方法は p(n - 2, 2) 通りになります。つまり、1 から k までを選んだあとの分割数を計算し、その総和を求めればいいわけです。

簡単な例を示しましょう。次の図を見てください。

p(6, 6) = p(5, 1)

        + p(4, 2) => p(3, 1) + p(2, 2)
                            => p(1, 1) + p(0, 2)

        + p(3, 3) => p(2, 1) + p(1, 2) + p(0, 3)

        + p(2, 4) => p(1, 1) + p(0, 2) 

        + p(1, 5)

        + p(0, 6)

        = 11 通り

p(6, 6) は p(5, 1) + p(4, 2) + p(3, 3) + p(2, 4) + p(1, 5) + p(0, 6) の総和になります。このうち、p(5, 1), p(1, 5), p(0, 6) は 1 になります。p(3, 3) は p(2, 1) + p(1, 2) + p(0, 3) になるので 3 通り、p(2, 4) は p(1, 1) + p(0, 2) になるので、2 通りになります。p(4, 2) はちょっと複雑です。p(4, 2) = p(3, 1) + p(2, 2) になります。ここで、p(2, 2) を求めると p(2, 2) = p(1, 1) + p(0, 2) になるので 2 通りになります。したがって、合計は 11 通りになります。

これをプログラムすると次のようになります。

リスト : 分割数

part_num(0, _) -> 1;
part_num(1, _) -> 1;
part_num(_, 1) -> 1;
part_num(N, K) when N < 0; K < 1 -> 0;
part_num(N, K) ->
  part_num(N - K, K) + part_num(N, K - 1).

part_num(N) -> part_num(N, N).

実際の処理は述語 part_num で行います。最初の 3 つの規則で、分割数が 1 になる場合を定義しています。次の規則は N が負または K が 1 未満の場合を表します。この場合、分割数は 0 になります。最後の規則で、p(n - 1, 1) + ... + p(n - k, k) を計算します。プログラムでは K の値をひとつずつ減らしていることに注意してください。なお、このプログラムはナイーブな実装なため、実行速度はとても遅いです。ご注意くださいませ。

-- 参考文献 --------
[1] 奥村晴彦,『C言語による最新アルゴリズム事典』, 技術評論社, 1991

●解答73

リスト : 整数の分割

part_int(F, 0, _, A) -> F(lists:reverse(A));
part_int(F, 1, _, A) -> F(lists:reverse([1 | A]));
part_int(F, N, 1, A) -> F(lists:reverse(yaep:make_list(1, N) ++ A));
part_int(F, N, K, A) ->
  if 
    N - K >= 0 -> part_int(F, N - K, K, [K | A]);
    true -> false
  end,
  part_int(F, N, K - 1, A).

partition_of_integer(F, N) -> part_int(F, N, N, []).

基本的な考え方は partition_number と同じです。関数 part_int に累積変数 A を追加して、選んだ数値を A に格納していくだけです。N が 0 の場合は F を評価し、N が 1 の場合は A に 1 を追加してから F を評価します。K が 1 の場合は make_list で要素が 1 で長さが N のリストを作成します。そして、それを演算子 ++ で A と連結してから F を評価します。最後の規則で、N - K が 0 以上であれば part_int を再帰呼び出しします。そのあとで、K の値を -1 して part_int を再帰呼び出しします。

●解答74

リスト : 完全順列

perfect_perm(F, _, [], A) -> F(lists:reverse(A));
perfect_perm(F, N, Xs, A) ->
  lists:foreach(
    fun(X) -> 
      if
        N =/= X -> perfect_perm(F, N + 1, lists:delete(X, Xs), [X | A]);
        true -> false
      end
    end,
    Xs).
perfect_permutation(F, N) -> perfect_perm(F, 1, iota(1 , N), []).

perfect_permutation は簡単です。実際の処理は関数 perfect_perm で行います。iota で 1 から N までの数値を格納したリストを生成し、それを引数 Xs に渡します。引数 N が順番を表します。lists:foreach の無名関数で、数字 X が N と等しくない場合、その数字を選択することできます。等しい場合は選択しません。Xs が空リストになったら、reverse で A を反転して F を評価します。これで完全順列を生成することができます。

●解答75

リスト : 完全順列の総数

montmort_number(1) -> 0;
montmort_number(2) -> 1;
montmort_number(N) when N > 2 ->
  (N - 1) * (montmort_number(N - 1) + montmort_number(N - 2)).

% 別解
montmort_number1(N, N, A, _) -> A;
montmort_number1(I, N, A, B) -> montmort_number1(I + 1, N, B, (I + 1) * (A + B)).
mont_mort_number1(N) when N >= 1 -> montmort_number1(1, N, 0, 1).

関数 montmort_number は公式をそのままプログラムしただけです。二重再帰になっているので、実行速度は大変遅くなります。これを繰り返しに変換すると別解のようになります。考え方はフィボナッチ数列と同じです。累積変数 A に i 番目の値を、B に i + 1 番目の値を保存しておきます。すると、i + 2 番目の値は (I + 1) * (A + B) で計算することができます。あとは、B の値を A に、新しい値を B にセットして処理を繰り返すだけです。

●解答76

集合を分割するアルゴリズムは簡単です。たとえば、n -1 個の要素 x1, ..., xn-1 を持つ集合を分割したところ、i 個の部分集合 S1, ..., Si が生成されたとしましょう。ここに、n 番目の要素 xn を追加すると、要素が n 個の集合を分割することができます。

新しい要素を追加する場合は次に示す手順で行います。

  1. 部分集合 Sk (k = 1 から i まで) に要素 xn を追加する
  2. 新しい部分集合 Si+1 (要素が xn だけの集合) を生成する

簡単な例を示しましょう。次の図を見てください。

部分集合を格納するリストを用意します。最初、部分集合は空集合なので空リストに初期化します。次に、要素 1 を追加します。部分集合は空リストなので、手順 1 は適用できません。手順 2 を適用して新しい部分集合 [1] を追加します。

次に要素 2 を追加します。[[1]] に 手順 1 を適用すると、部分集合 [1] に要素を追加して [[1, 2]] になります。手順 2 を適用すると、新しい部分集合 [2] を追加して [[1], [2]] になります。最後に 3 を追加します。[[1, 2]] に手順 1 を適用すると [[1, 2, 3]] に、手順 2 を適用すると [[1, 2], [3]] になります。[[1], [2]] に手順 1 を適用すると [[1, 3], [2]] と [[1], [2, 3]] になり、手順 2 を適用すると [[1], [2], [3]] になります。

このように、簡単な方法で集合を分割することができます。実際にプログラムを作る場合、上図を木と考えて、深さ優先で木をたどると簡単です。次のリストを見てください。

リスト : 集合の分割

part_set(F, [], A) -> F(A);
part_set(F, [X | Xs], A) ->
  lists:foreach(fun(Y) -> part_set(F, Xs, [[X | Y] | lists:delete(Y, A)]) end, A),
  part_set(F, Xs, [[X] | A]).
partition_of_set(F, Xs) -> part_set(F, lists:reverse(Xs), []).

実際の処理は関数 part_set で行います。最初の規則が再帰呼び出しの停止条件です。次の規則の lists:foreach で、部分集合に要素 X を追加します。無名関数 でリスト A から要素 Y を順番に取り出し、A から Y を取り除いたリストに [X | Y] を追加します。最後に、新しい部分集合 [X] を A に追加します。ただし、このままでは要素の並び方が逆順になるので、part_set を呼び出す前に reverse でリスト Xs を反転しています。これで集合の分割をすべて求めることができます。

●解答77

リスト : ベル数

fold_with_index(_, _, A, []) -> A;
fold_with_index(F, I, A, [X | Xs]) ->
  fold_with_index(F, I + 1, F(X, I, A), Xs).

bell_number(N, N, [X | _]) -> X;
bell_number(I, N, Bs) ->
  bell_number(I + 1,
              N,
              [fold_with_index(
                 fun(X, K, A) -> A + comb_num(I, K) * X end,
                 0,
                 0,
                 Bs) | Bs]).
bell_number(N) -> bell_number(0, N, [1]).

bell_number は公式をそのままプログラムするだけです。累積変数 Bs にベル数を逆順で格納します。nk は関数 comb_num で求めます。nk * B(k) の総和は関数 fold_with_index で計算します。fold_with_index は添字を関数に渡して畳み込みを行います。無名関数の引数 X がリストの要素、K が添字、A が累積変数です。Bs は逆順になっていますが、二項係数は ninn - i の値が同じになるので、そのまま計算しても大丈夫です。もちろん、reverse で Bs を逆順にしてから計算してもかまいません。

●解答78

リスト : 集合のグループ分け

group_part(F, _, _, [], A) -> F(A);
group_part(F, N, M, [X | Xs], A) ->
  lists:foreach(fun(Y) ->
      if
        length(Y) < N -> group_part(F, N, M, Xs, [[X | Y] | lists:delete(Y, A)]);
        true -> false
      end
    end,
    A),
  if
    length(A) < M -> group_part(F, N, M, Xs, [[X] | A]);
    true -> ok
  end.
group_partition(F, N, M, Xs) -> group_part(F, N, M, lists:reverse(Xs), []).

group_partition は partition_of_set を改造するだけで簡単に作成することができます。生成する部分集合の大きさを N に、部分集合の個数を M に制限するだけです。部分集合 Y に X を追加する場合、length(Y) < N であることをチェックします。新しい部分集合 [X] を追加する場合、length(A) < M であることをチェックします。これで集合をグループに分けることができます。

●解答79

グループ分けの総数は次の式で求めることができます。

k = n * m
kn * k-nn * k-2*nn * ... * 2*nn * nn / m!

たとえば、n = 3, m = 5 の場合は次のようになります。

153 * 123 * 93 * 63 * 33 / 5! = 1401400

これをそのままプログラムすると次のようになります。

リスト : グループ分けの総数

fact(0) -> 1;
fact(N) when N > 0 -> N * fact(N - 1).

group_part_num(0, _, M, A) -> A div fact(M);
group_part_num(K, N, M, A) -> group_part_num(K - N, N, M, A * comb_num(K, N)).

group_partition_number(N, M) -> group_part_num(N * M, N, M, 1).

階乗は関数 fact で、組み合わせの個数は関数 comb_num で計算します。要素の個数を変数 K にセットし、累積変数 a に comb_num(K, N) を乗算します。あとは K から N を減算し、K が 0 でなければ処理を繰り返すだけです。最後に A div fact(M) を計算して返します。

●解答80

参考文献 [1] の「式の評価」によると、四則演算の数式は次の構文規則で表すことができます。

式 := 項 (+ | -) 項 (+ | -) 項 ...
項 :- 因子 (* | /) 因子 (* | /) 因子 ...
因子 := 数 | (式)

これをそのままプログラムすると、次のようになります。

リスト : 数式の計算 (中置記法)

% 因子の評価
factor([X | Xs]) when is_number(X) -> {X, Xs};
factor([X | Xs]) when is_list(X) -> {expression(X), Xs}.

% 項の評価
term_sub(V, [X | Xs]) when X =:= '*' ->
  {Y, Ys} = factor(Xs), term_sub(V * Y, Ys);
term_sub(V, [X | Xs]) when X =:= '/' ->
  {Y, Ys} = factor(Xs), term_sub(V / Y, Ys);
term_sub(V, Xs) -> {V, Xs}.

term(Xs) -> {Y, Ys} = factor(Xs), term_sub(Y, Ys).

% 式の評価
expr_sub(V, []) -> V;
expr_sub(V, [X | Xs]) when X =:= '+' ->
  {Y, Ys} = term(Xs), expr_sub(V + Y, Ys);
expr_sub(V, [X | Xs]) when X =:= '-' ->
  {Y, Ys} = term(Xs), expr_sub(V - Y, Ys);

expression(Xs) -> {Y, Ys} = term(Xs), expr_sub(Y, Ys).

関数 expression は「式」を評価します。最初に関数 term を呼び出して「項」を評価します。次に関数 expr_sub を呼び出します。最初の節で、リストが空であれば評価結果 V を返します。演算子が + または - の場合は term を呼び出して評価を行い、返り値を Y と Ys にセットします。そして、V + Y または V - Y を計算します。

関数 term も同様の処理を行います。この場合は最初に関数 factor を呼び出して「因子」を評価します。そして、演算子が * または / の場合は factor を呼び出して評価を続行します。そうでなければ、評価結果 V と残りのリスト Xs をタプルに格納して返します。関数 factor は簡単で、リストの先頭要素 X が数値の場合はそれをそのまま返し、リストであればそれを expression に渡して評価します。

数値の判定は組み込み関数 is_number で、リストの判定は組み込み関数 is_list で行うことができます。それ以外の場合はマッチングしないのでエラーになります。

-- 参考文献 --------
[1] 奥村晴彦,『C言語による最新アルゴリズム事典』, 技術評論社, 1991

Copyright (C) 2011 Makoto Hiroi
All rights reserved.

[ PrevPage | Erlang | NextPage ]