From ok@atlas.otago.ac.nz Thu Jun 14 02:12:06 2001
Received: from atlas.otago.ac.nz (atlas.otago.ac.nz [139.80.32.250])
	by swi.psy.uva.nl (8.11.2/8.11.2) with ESMTP id f5E0C4322479
	for <prolog@swi.psy.uva.nl>; Thu, 14 Jun 2001 02:12:05 +0200 (MET DST)
Received: (from ok@localhost)
	by atlas.otago.ac.nz (8.9.3/8.9.3) id MAA73875;
	Thu, 14 Jun 2001 12:11:59 +1200 (NZST)
Date: Thu, 14 Jun 2001 12:11:59 +1200 (NZST)
From: "Richard A. O'Keefe" <ok@atlas.otago.ac.nz>
Message-Id: <200106140011.MAA73875@atlas.otago.ac.nz>
To: cjcheng@es.co.nz, prolog@swi.psy.uva.nl
Subject: Re:  [SWIPL] possible combinations of the sum.

"cjcheng" <cjcheng@es.co.nz> 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.

