自然数 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
自然数 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
自然数 N の約数の合計値 M を求める述語 divisor_sum(N, M) を定義してください。
?- divisor_sum(12, M). M = 28 ; No ?- divisor_sum(12345678, M). M = 27319968 ; No
自然数 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
整数 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
整数 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
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
完全順列の総数を「モンモール数 (Montmort number) 」といいます。モンモール数は次の漸化式で求めることができます。
モンモール数を求める述語 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
リストで表した集合 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
集合を分割する方法の総数を「ベル数 (Bell Number) 」といい、次の漸化式で求めることができます。
ベル数を求める述語 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
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
集合を 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
リスト : 素因数分解
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 がその値で割り切れることはありません。
n の素因数分解ができると、約数の個数を求めるのは簡単です。\(n = p^a \times q^b \times r^c\) とすると、約数の個数は \((a + 1) \times (b + 1) \times (c + 1)\) になります。たとえば、12 は \(2^2 \times 3^1\) になるので、約数の個数は 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) を掛け算していくだけです。
n の素因数分解ができると、約数の合計値を求めるのは簡単です。n の素因数分解が \(p^a\) だった場合、その約数の合計値は次の式で求めることができます。
たとえば、8 の素因数分解は \(2^3\) になり、素数の合計値は 8 + 4 + 2 + 1 = 15 になります。
\(p^a\) の約数の合計値を \(\sigma(p, a)\) で表すことにします。\(n = p^a \times q^b \times r^c\) の場合、\(n\) の約数の合計値は \(\sigma(p, a) \times \sigma(q, b) \times \sigma(r, c)\) になります。たとえば、12 は \(2^2 \times 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 に掛け算していくだけです。
p が素数の場合、\(p^a\) の約数は次のように簡単に求めることができます。
n の素因数分解が \(p^a \times q^b\) だったとすると、その約数は次のようになります。
たとえば、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 で昇順に整列します。
整数 n を k 以下で分割する総数を求める関数を p(n, k) で表します。参考文献『Ｃ言語による最新アルゴリズム事典』によると、p(n, 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 の値をひとつずつ減らしていることに注意してください。なお、このプログラムはナイーブな実装なため、実行速度はとても遅いです。ご注意くださいませ。
リスト : 整数の分割
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 未満の場合は失敗してバックトラックすることになります。これで分割の仕方をすべて求めることができます。
リスト : 完全順列
/* 数列の生成 */
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 を反転します。これで完全順列を生成することができます。
リスト : 完全順列の総数
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) に渡して処理を繰り返すだけです。
集合を分割するアルゴリズムは簡単です。たとえば、n -1 個の要素 x1, ..., xn-1 を持つ集合を分割したところ、i 個の部分集合 S1, ..., Si が生成されたとしましょう。ここに、n 番目の要素 xn を追加すると、要素が n 個の集合を分割することができます。
新しい要素を追加する場合は次に示す手順で行います。
簡単な例を示しましょう。次の図を見てください。
() ─ ((1)) ─┬─ ((1 2)) ─┬─ ((1 2 3))
│ │
│ └─ ((1 2) (3))
│
└─ ((1) (2)) ─┬─ ((1 3) (2))
│
├─ ((1) (2 3))
│
└─ ((1) (2) (3))
図 : 集合 (1 2 3) を分割する
部分集合を格納するリストを用意します。最初、部分集合は空集合なので空リストに初期化します。次に、要素 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 を反転しています。これで集合の分割をすべて求めることができます。
リスト : ベル数
% 組み合わせの数
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 にベル数を逆順で格納します。nＣk は述語 comb_num で求めます。nＣk * B(k) の総和は述語 bell_next で計算します。
bell_next の最初の規則が再帰呼び出しの停止条件です。Bs は逆順になっていますが、二項係数は nＣk と nＣn - k の値が同じになるので、そのまま計算しても大丈夫です。述語 bell_number_sub は bell_next でベル数を求め、それを累積変数 Bs に追加します。 第 1 引数 I と第 2 引数 N が等しい場合、Bs の先頭要素が求めるベル数になります。述語 bell_number は bell_number_sub を呼び出すだけです。このとき、Bs の初期値は [1] になります。
リスト : 集合のグループ分け
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 よりも小さいことを確認します。これで集合をグループに分けることができます。
グループ分けの総数は次の式で求めることができます。
たとえば、n = 3, m = 5 の場合は次のようになります。
これをそのままプログラムすると次のようになります。
リスト : グループ分けの総数
/* 階乗 */
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 を呼び出すだけです。