Subject: Re: [SWIPL] possible combinations of the sum.

From: "Richard A. O'Keefe" <[email-masked]>
Date: Thu, 14 Jun 2001 12:11:59 +1200 (NZST)

"cjcheng" <[email-masked]> wrote:
	I am a novice of Prolog programming.
	I hope to write a predicate,which for a given integer N,
	can generate a list of lists, with each list can be summed up to N.
	e.g.,
	sum(5,X)
	[[5],[1,4],[2,3],[1,1,3],[1,2,2],[1,1,1,2],[1,1,1,1,1]].
	I already wrote one ,but if N>9, it will be really slow.

Of course, if you allow negative integers in these lists, there are
infinitely many ways to add up to N.  Presumably what you want is
    "Given a natural number N, find all the partitions of N."

A recursive definition would go something like this:

partitions 0 = [[]]
partitions n | n > 0 = union [partitions (n-x) `with` x | x <- [1..n]

([] `with` x) = []
((p:ps) `with` x) = (x:p):(ps `with` x)

The number of partitions grows faster than linearly; I forget what the
order is, and of course the size of the partitions grows linearly, so we
are talking about worse than quadratic growth.  Even so, the code I just
whipped up gives an answer for n=9 fairly quickly.