M.Hiroi's Home Page

Prolog Programming

Yet Another Prolog Problems

[ PrevPage | Prolog | NextPage ]

●問題88

自然数 N を素因数分解する述語 factorization(N, L) を定義してください。L はリスト [[p, q], ...] で、[p, q] は pq を表します。

?- factorization(12345678, L).

L = [[2, 1], [3, 2], [47, 1], [14593, 1]] ;

No
?- factorization(1234567890, L).

L = [[2, 1], [3, 2], [5, 1], [3607, 1], [3803, 1]] ;

No
?- factorization(1999999991, L).

L = [[11, 1], [349, 1], [520969, 1]] ;

No

解答88

●問題89

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

?- divisor_num(12345678, M).

M = 24 ;

No
?- divisor_num(1234567890, M).

M = 48 ;

No
?- divisor_num(1999999991, M).

M = 8 ;

No

解答89

●問題90

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

?- divisor_sum(12, M).

M = 28 ;

No
?- divisor_sum(12345678, M).

M = 27319968 ;

No

解答90

●問題91

自然数 N の約数をリスト L に格納する述語 divisor(N, L) を定義してください。

?- divisor(12, L).

L = [1, 2, 3, 4, 6, 12] ;

No
?- divisor(12345678, L), length(L, N).

L = [1, 2, 3, 6, 9, 18, 47, 94, 141|...],
N = 24 ;

No
?- divisor(1234567890, L), length(L, N).

L = [1, 2, 3, 5, 6, 9, 10, 15, 18|...],
N = 48 ;

No
?- divisor(1999999991, L), length(L, N).

L = [1, 11, 349, 3839, 520969, 5730659, 181818181, 1999999991],
N = 8 ;

No

解答91

●問題92

整数 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 の分割数 M を求める述語 partition_number(N, M) を定義してください。

?- between(1, 20, I), partition_number(I, N), write(N), nl, fail.
1
2
3
5
7
11
15
22
30
42
56
77
101
135
176
231
297
385
490
627

No

解答92

●問題93

整数 N の分割の仕方をすべて求める述語 partition_of_integer(N. L) を定義してください。

?- partition_of_integer(6, L), write(L), nl, fail.
[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]

No
?- partition_of_integer(7, L), write(L), nl, fail.
[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]

No

解答93

●問題94

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

?- perfect_permutation(4, X), write(X), nl, fail.
[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]

No

解答94

●問題95

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

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

モンモール数を求める述語 montmort_number(N, A) を定義してください。

?- between(1, 16, I), montmort_number(I, A), write(A), nl, fail.
0
1
2
9
44
265
1854
14833
133496
1334961
14684570
176214841
2290792932
32071101049
481066515734
7697064251745

No

解答95

●問題96

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

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

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

Ls の分割の仕方をすべて求める述語 partition_of_set(Ls, Xs) を定義してください。

?- partition_of_set([1,2,3], Ls), write(Ls), nl, fail.
[[1, 2, 3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 3], [2]]
[[1], [2], [3]]

No
?- partition_of_set([1,2,3,4], Ls), write(Ls), nl, fail.
[[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]]

No

解答96

●問題97

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

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

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

?- between(0, 10, I), bell_number(I, A), write(A), nl, fail.
1
1
2
5
15
52
203
877
4140
21147
115975

No

解答97

●問題98

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

?- group_partition(2, 2, [1,2,3,4], X), write(X), nl, fail.
[[1, 2], [3, 4]]
[[1, 4], [2, 3]]
[[1, 3], [2, 4]]

No
?- group_partition(2, 3, [1,2,3,4,5,6], X), write(X), nl, fail.
[[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]]

No

解答98

●問題99

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

?- group_partition_number(2,2,X).

X = 3 ;

No
?- group_partition_number(2,3,X).

X = 15 ;

No
?- group_partition_number(3,3,X).

X = 280 ;

No
?- group_partition_number(3,4,X).

X = 15400 ;

No
?- group_partition_number(3,5,X).

X = 1401400 ;

No

解答99


●解答88

リスト : 素因数分解

factor_sub(N, M, C, [N, C]) :- N mod M =\= 0.
factor_sub(N, M, C, Z) :-
    N mod M =:= 0,
    A is N / M,
    C1 is C + 1,
    factor_sub(A, M, C1, Z).

factor_loop(I, N, Acc, Ans) :-
    N < I * I,
    (N > 1 -> reverse([[N, 1] | Acc], Ans) ; reverse(Acc, Ans)).
factor_loop(I, N, Acc, Ans) :-
    N >= I * I,
    factor_sub(N, I, 0, [M, C]),
    I2 is I + 2,
    (C > 0 -> factor_loop(I2, M, [[I, C] | Acc], Ans) ; factor_loop(I2, N, Acc, Ans)).

factorization(N, Ans) :-
    factor_sub(N, 2, 0, [M, C]),
    (C > 0 -> factor_loop(3, M, [[2, C]], Ans) ; factor_loop(3, N, [], Ans)).

素因数分解は素数 2, 3, 5, ... で順番に割り算していけばいいのですが、いちいち素数を求めるのは大変なので、2 と 3 以上の奇数列で割り算していきます。述語 factor_sub は N を M で割り算します。このとき、M で割り切れる回数 C と余り N を求めます。

述語 factor_loop は数値 N を奇数 I で割り算していきます。最初の規則で、N < I * I (√N < I) になったら繰り返しを終了します。N が 1 よりも大きい場合は、累積変数 Acc に [N, 1] を追加してから reverse で反転します。そうでなければ reverse で反転するだけです。次の規則では、factor_sub を呼び出して I で割った回数 C と余り M を求めます。C が 0 よりも大きい場合は Acc に [I, C] を追加します。あとは I を +2 してから factor_loop を再帰呼び出しします。

述語 factorization は、最初に factor_sub を呼び出して N を 2 で割り算します。C が 0 よりも大きい場合、factor_sub の累積変数 (第 3 引数) の初期値は [[2, C]] になります。そうでなければ空リストになります。奇数列には素数ではないものがありますが、その前に小さな素数で素因数分解されているので、N がその値で割り切れることはありません。

●解答89

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 個です。

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

リスト : 約数の個数

% 畳み込み
fold_left(_, A, [], A).
fold_left(F, A, [X | Xs], C) :-
    call(F, A, X, B), fold_left(F, B, Xs, C).

divisor_num1(A, [_, X], B) :- B is A * (X + 1).
divisor_num(N, Ans) :- 
   factorization(N, Ls), fold_left(divisor_num1, 1, Ls, Ans).

divisor_num は fold_left を使って累積変数 A に (X + 1) を掛け算していくだけです。

●解答90

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 になります。

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

リスト : 約数の合計値

prime_sum(_, 0, Acc, Ans) :- Ans is Acc + 1.
prime_sum(P, N, Acc, Ans) :-
    N < 0,
    N1 is N - 1,
    Acc1 is Acc + P ^ N,
    prime_sum(P, N1, Acc1, Ans).

divisor_sum1(Acc, [P, N], Ans) :- prime_sum(P, N, 0, X), Ans is Acc * X.
divisor_sum(N, Ans) :-
    factorization(N, Ls), fold_left(divisor_sum1, 1, Ls, Ans).

述語 prime_sum は σ(p, n) を計算します。あとは fold_left で prime_sum で求めた値 X を累積変数 Acc に掛け算していくだけです。

●解答91

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, Acc, [1 | Acc]).
divisor_sub(P, N, Acc, Ans) :-
    N > 0,
    M is P ^ N,
    N1 is N - 1,
    divisor_sub(P, N1, [M | Acc], Ans).

divisor_product(Xs, Ys, Z) :-
    member(X, Xs), member(Y, Ys), Z is X * Y.

divisor_sub1([], Ans, Ans).
divisor_sub1([[P, N] | Xs], Acc, Ans) :-
    divisor_sub(P, N, [], Ys),
    findall(Z, divisor_product(Acc, Ys, Z), Acc1),
    divisor_sub1(Xs, Acc1, Ans).

divisor(N, L) :-
    factorization(N, Xs),
    divisor_sub1(Xs, [1], Ys),
    sort(Ys, L).

述語 divisor_sub は pn の約数を求めてリストに格納します。述語 divisor_product は 2 つのリスト Xs, Ys の要素を乗算し、その値が Z になります。述語 divisor_sub1 は第 1 引数のリストから [P, N] を取り出し、divisor_sub でその約数を Ys に求めます。そして、divisor_product で累積変数 Acc と Ys の要素を乗算し、その結果を findall でリスト Acc1 に格納します。この処理を第 1 引数が空リストになるまで繰り返します。述語 divisor は factorization を呼び出し、divisor_sub1 で約数を求め、それを sort で昇順に整列します。

●解答92

整数 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, 0) :- (N < 0 ; K < 1), !.

part_num(N, K, A) :-
    N1 is N - K,
    part_num(N1, K, A1),
    K1 is K - 1,
    part_num(N, K1, A2),
    A is A1 + A2.

partition_number(N, A) :- part_num(N, N, A).

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

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

●解答93

リスト : 整数の分割

part_int(0, _, []) :- !.

part_int(N, K, [K | A]) :-
    N1 is N - K,
    N1 >= 0,
    part_int(N1, K, A).

part_int(N, K, A) :-
    K1 is K - 1,
    K1 >= 1,
    part_int(N, K1, A).

partition_of_integer(N, A) :- part_int(N, N, A).

基本的な考え方は partition_number と同じです。実際の処理は述語 part_int で行います。最初の規則は N が 0 の場合です。分割する整数がないので空リストになります。これが再帰呼び出しの停止条件になります。次の規則は整数 N から K を選択する場合です。N - K が 0 以上であれば K を選択できるので、part_int を再帰呼び出ししてリスト A に K を追加します。

N - K が負になった場合は 3 番目の規則が選択されます。ここで K の値を -1 して part_int を再帰呼び出しします。K - 1 が 1 未満の場合は失敗してバックトラックすることになります。これで分割の仕方をすべて求めることができます。

●解答94

リスト : 完全順列

/* 数列の生成 */
iota(N, M, []) :- N > M.
iota(N, M, [N | Xs]) :-
    N =< M, N1 is N + 1, iota(N1, M, Xs).

perfect_perm_sub(_, [], Acc, Ans) :- reverse(Acc, Ans).
perfect_perm_sub(N, Ls, Acc, Ans) :-
    select(X, Ls, Xs),
    N =\= X,
    N1 is N + 1,
    perfect_perm_sub(N1, Xs, [X | Acc], Ans).
perfect_permutation(M, Ans) :-
    iota(1, M, Ls),
    perfect_perm_sub(1, Ls, [], Ans).

perfect_permutation は簡単です。実際の処理は述語 perfect_perm_sub で行います。iota で 1 から M までの数値を格納したリストを生成し、それを引数 Ls に渡します。第 1 引数 N が順番を表します。select で Ls から要素 X を選び、X が N と等しくない場合、その数字を選択することできます。等しい場合は選択しません。Ls が空リストになったら、reverse で累積変数 Acc を反転します。これで完全順列を生成することができます。

●解答95

リスト : 完全順列の総数

montmort_number(1, 0).
montmort_number(2, 1).
montmort_number(N, A) :-
    N > 2,
    N1 is N - 1,
    montmort_number(N1, A1),
    N2 is N - 2,
    montmort_number(N2, A2),
    A is N1 * (A1 + A2).

% 別解
montmort_sub(N, N, A, _, A).
montmort_sub(I, N, A, B, Ans) :-
    I < N,
    I1 is I + 1,
    A1 is I1 * (A + B),
    montmort_sub(I1, N, B, A1, Ans).
montmort_number_fast(N, A) :- montmort_sub(1, N, 0, 1, A).

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

●解答96

集合を分割するアルゴリズムは簡単です。たとえば、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([], Ys, Ys).
part_set([X | Xs], Ys, A) :-
    select(Z, Ys, Zs),
    part_set(Xs, [[X | Z] | Zs], A).
part_set([X | Xs], Ys, A) :-
    part_set(Xs, [[X] | Ys], A).

partition_of_set(Xs, Ys) :- 
    reverse(Xs, Xs1), part_set(Xs1, [], Ys).

実際の処理は述語 part_set で行います。最初の規則が再帰呼び出しの停止条件です。次の規則は部分集合に要素 X を追加する処理です。select でリスト Ys から要素 Z をひとつ選び、Z の先頭に X を追加します。Zs には Ys から Z を取り除いたリストが格納されているので、[[X | Z] | Zs] とすることで部分集合に X を追加することができます。

select が失敗すると、最後の規則が選択されます。ここで Ys に新しい部分集合 [X] を追加します。ただし、このままでは要素の並び方が逆順になるので、part_set を呼び出す前に reverse でリスト Xs を反転しています。これで集合の分割をすべて求めることができます。

●解答97

リスト : ベル数

% 組み合わせの数
comb_num(_,0,1).
comb_num(N, N, 1) :- N > 0.
comb_num(N, R, M) :-
  R > 0, N =\= R, R1 is R - 1, comb_num(N, R1, A), M is A * (N - R + 1) / R.

% ベル数
bell_next(_, _, [], Acc, Acc).
bell_next(N, K, [B | Bs], Acc, Ans) :-
    comb_num(N, K, C),
    Acc1 is Acc + C * B,
    K1 is K + 1,
    bell_next(N, K1, Bs, Acc1, Ans).

bell_number_sub(N, N, [A | _], A).
bell_number_sub(I, N, Bs, A) :-
    I < N,
    bell_next(I, 0, Bs, 0, N1),
    I1 is I + 1,
    bell_number_sub(I1, N, [N1 | Bs], A).

bell_number(N, A) :-
    bell_number_sub(0, N, [1], A).

bell_number は公式をそのままプログラムするだけです。実際の処理は述語 bell_number_sub で行います。累積変数 bs にベル数を逆順で格納します。nk は述語 comb_num で求めます。nk * B(k) の総和は述語 bell_next で計算します。

bell_next の最初の規則が再帰呼び出しの停止条件です。Bs は逆順になっていますが、二項係数は nknn - k の値が同じになるので、そのまま計算しても大丈夫です。述語 bell_number_sub は bell_next でベル数を求め、それを累積変数 Bs に追加します。 第 1 引数 I と第 2 引数 N が等しい場合、Bs の先頭要素が求めるベル数になります。述語 bell_number は bell_number_sub を呼び出すだけです。このとき、Bs の初期値は [1] になります。

●解答98

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

group_part(_, _, [], Ys, Ys).
group_part(N, M, [X | Xs], Ys, A) :-
    select(Z, Ys, Zs),
    length(Z, N1),
    N1 < N,
    group_part(N, M, Xs, [[X | Z] | Zs], A).
group_part(N, M, [X | Xs], Ys, A) :-
    length(Ys, M1),
    M1 < M,
    group_part(N, M, Xs, [[X] | Ys], A).

group_partition(N, M, Xs, Ys) :- 
    reverse(Xs, Xs1), group_part(N, M, Xs1, [], Ys).

group_partition は partition_of_set を改造するだけで簡単に作成することができます。生成する部分集合の大きさを N に、部分集合の個数を M に制限するだけです。述語 group_part の 2 番目の規則で、部分集合 Z に X を追加するとき、length で Z の長さを求め、それが N よりも小さいことを確認します。3 番目の規則で [X] を Ys に追加するとき、length で Ys の長さを求め、それが M よりも小さいことを確認します。これで集合をグループに分けることができます。

●解答99

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

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, A) :-
    N > 0, N1 is N - 1, fact(N1, A1), A is N * A1.

group_part_sub(0, N, M, Acc, A) :- 
    fact(M, X),
    A is Acc // X.
group_part_sub(K, N, M, Acc, A) :-
    K > 0,
    K1 is K - N,
    comb_num(K, N, X),
    Acc1 is Acc * X,
    group_part_sub(K1, N, M, Acc1, A).
group_partition_number(N, M, A) :-
    K is N * M,
    group_part_sub(K, N, M, 1, A).

実際の処理は述語 group_part_sub で行います。階乗は述語 fact で、組み合わせの数は述語 comb_num で計算します。最初の規則で、第 1 引数が 0 になったら fact で M! を求め、その値 X で Acc を割り算します。次の規則で、組み合わせの数を comb_num で求めて Acc と掛け算します。そして、K から N を引き算して group_part_sub を再帰呼び出しします。group_partition_number は group_part_sub を呼び出すだけです。


Copyright (C) 2011 Makoto Hiroi
All rights reserved.

[ PrevPage | Prolog | NextPage ]