% The partitions of an integer are the ways to write it as a sum of positive % integers, disregarding order. % These are implementations of Algorithm P and Algorithm H from section 7.2.1.4 % of pre-fascicle 3B of "The Art of Computer Programming" by Donald E. Knuth. %%%%%%%%%%%%%%% % Algorithm P % %%%%%%%%%%%%%%% % partition(N, Partition) is true if Partition is a partition of the integer N. % On backtracking, all partitions will be found, in reverse co-lexicographic % order. % e.g. findall(X, partition(5, X), Xs) % gives Xs=[[5], [1,4], [2,3], [1,1,3], [1,2,2], [1,1,1,2], [1,1,1,1,1]] partition(1, [1]):-!. partition(N, Partition):- N > 1, partition_1([N], 0, _, Partition). % e.g. findall(X, partition_1([5], 0, _, X), Xs) % gives Xs=[[5], [1,4], [2,3], [1,1,3], [1,2,2], [1,1,1,2], [1,1,1,1,1]] partition_1([N], 0, 0, [N]). partition_1(As, M0, M, Partition):- next_partition(As, M0, M, Bs), % A Partition consists of M ones followed by the elements of Bs prepend_ones(M, Bs, Partition). partition_1(As, M0, M, Partition):- next_partition(As, M0, M1, Bs), partition_1(Bs, M1, M, Partition). % Finds the next partition. % e.g. next_partition([2,5], 1, M, As) gives M=3, As=[5] % that is, the partition after [1,2,5] is [1,1,1,5] % e.g. next_partition([3,3], 2, M, As) gives M=1, As=[2,2,3] % that is, the partition after [1,1,3,3] is [1,2,2,3] % e.g. next_partition([3,4], 1, M, As) gives M=0, As=[2,2,4] % that is, the partition after [1,3,4] is [2,2,4] next_partition([2|As], M0, M, As):-!, % The easy case: Increase number of leading ones by 2, and remove 2 from As M is M0 + 2. next_partition([X1|As], M0, M, Bs):- % The harder case: X is X1 - 1, N is X1 + M0, next_partition_1(N, X, M0, As, M, Bs). % next_partition_1(N, X, M0, As, M, Bs) is true if Bs is the result of % prepending I occurrences of X to As preceded by J if J > 1, and % M = M0 + [J = 1], where I = N div X and J = N mod X. % e.g. next_partition_1(5, 2, 2, [3], M, Bs) gives M=1, Bs=[2,2,3] next_partition_1(N, _, _, As, N, As):- % 0 <= N <= 1: There are N leading ones, and As is unchanged N < 2, !. next_partition_1(N, X, _, As, 0, [N|As]):- % 2 <= N < X: There are no leading ones, and N is prepended to As N < X, !. next_partition_1(N, X, M0, As, M, Bs):- % N >= X: The number of leading ones is unchanged, and X is prepended to As N1 is N - X, next_partition_1(N1, X, M0, [X|As], M, Bs). % prepend_ones(N, Xs, Ys) is true if Ys is the result of prepending N ones % to the elements of Xs. % e.g. prepend_ones(3, [2,3], Ys) gives Ys=[1,1,1,2,3] prepend_ones(0, Xs, Xs):-!. prepend_ones(N, Xs, [1|Ys]):- N1 is N - 1, prepend_ones(N1, Xs, Ys). %%%%%%%%%%%%%%% % Algorithm H % %%%%%%%%%%%%%%% % m_partition(N, M, Partition) is true if Partition is a partition of the % integer N containing M parts. On backtracking, all partitions will be % found, in co-lexicographic order. % e.g. findall(X, m_partition(10, 3, X), Xs) % gives Xs=[[8,1,1],[7,2,1],[6,3,1],[5,4,1],[6,2,2],[5,3,2],[4,4,2],[4,3,3]] m_partition(N, M, Partition):- M >= 2, N >= M, M1 is M - 1, A is N - M1, prepend_ones(M1, [], Ones), m_partition_1([A|Ones], Partition). m_partition_1(As, As). m_partition_1(As, Bs):- m_partition_2(As, Bs). m_partition_2(As, Bs):- next_m_partition(As, Bs). m_partition_2(As, Bs):- next_m_partition(As, Cs), m_partition_2(Cs, Bs). % Finds the next Partition. % e.g. next_m_partition([6,3,1,1], Xs) gives Xs=[5,4,1,1] % e.g. next_m_partition([4,3,3,1], Xs) gives Xs=[5,2,2,2] next_m_partition([A1,A2|As], Partition):- % The easy case: A2 < A1 - 1, !, B1 is A1 - 1, B2 is A2 + 1, Partition=[B1,B2|As]. next_m_partition([A1,A2|As], Partition):- % The harder case: S0 is A1 + A2 - 1, next_m_partition_1(As, A1, S0, 3, S, J, Cs), Cs=[X|_], next_m_partition_2(J, S, X, Cs, Partition). % next_m_partition_1(As, A1, S0, 3, S, J, Bs) is true if the first element of % As which is less than A1-1 is the J-th element, Bs are the elements of % As starting at the J-th element, except that the first element of Bs is % incremented by one, and S=S0+A_3+...+A_(J-1). % e.g. next_m_partition_1([3,1], 4, 6, 3, S, J, Ks) gives S=9, J=4, Ks=[2] next_m_partition_1([Aj|As], A1, S, J, S, J, [Bj|As]):- Aj < A1 - 1, !, Bj is Aj + 1. next_m_partition_1([Aj|As], A1, S0, J0, S, J, Bs):- S1 is S0 + Aj, J1 is J0 + 1, next_m_partition_1(As, A1, S1, J1, S, J, Bs). % next_m_partition_2(J, S, X, Cs, Partition) is true if Partition is the result % of prepending J-1 integers to Cs, each integer being X, except the first, % which is S-(J-2)*X. % e.g. next_m_partition_2(4, 9, 2, [2], Xs) gives Xs=[5,2,2,2] next_m_partition_2(2, S, _, Cs, [S|Cs]):-!. next_m_partition_2(J, S, X, Cs, Bs):- S1 is S - X, J1 is J - 1, next_m_partition_2(J1, S1, X, [X|Cs], Bs).