All Partitions of an Integer

% 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).

LPA Index     Home Page

Valid HTML 4.01 Strict