Re: some quick help with lists

From: Matthew Huntbach (mmh_at_dcs.qmul.ac.uk)
Date: 11/23/04 

Date: Tue, 23 Nov 2004 09:26:57 +0000

On Mon, 22 Nov 2004, dirty_bit wrote:

> What I thought would be a simple first program to write in Prolog has
> some how become a problem. I am attempting to write a rule that takes
> a list and an integer. The integer is the sum of two elements in the
> list. (e.g. sum(list, num) ).
>
> I was trying to do something along the lines of:
>
> sum([H|T], A) :- select([H|T],X1,T2), select(T2,X2,_), A is +(X1,X2).
>
> This works just fine, but I would like for it to also be able to go
> the other way too. For example if I gave it sum(X, 3). X would equal:
> [1,2], [2,1], [1,2,3], etc. And it would need to stop at a certain
> list length that I could specify so it doesn't loop forever.
>
> Any suggestions would be greatly appreciated. Perhaps my code needs to
> be completely rewritten?
>
First of all, the arithmetic operations do not work backwards in Prolog.
So you cannot have A is X1+X2, with A bound and X1 and X2 unbound, and
expect it to backtrack and supply all possible integers that add to A.

However, it is fairly easy to write a predicate which has the same
effect. Given N, all you need is for it to bind two variables to 1 and N-1,
then to backtrack and bind them to 2,N-2, then to 3,N-3 and so on down to
N-1,1. Here:

addsup(N,N1,N2) :- addsup1(N,1,N1,N2).

addsup1(N,N,_,_) :- !,fail.
addsup1(N,D,D,N1) :- N1 is N-D.
addsup1(N,D,N1,N2) :- D1 is D+1,addsup1(N,D1,N1,N2).

The first clause for addsup1 is so that backtracking stops at N-1,1 and
does not go on to 0,N followed by -1,N+1 and so on. You did not say,
but your example suggests, that when you wrote "integer" you meant
"positive integer".

Well, this is fine to generate all lists of length 2 that answer your
problem. But what other lists do you want generated and in what
order? There are, after all, an infinite number of three element lists
that answer your problem. If you give it sum(X,N) with N bound to
an integer, for every pair N1,N2 which sums to N, there is the infinite
series of lists [N1,N2,1], [N1,N2,2], [N1,N2,3] and so on. Then there's
the infinite series of lists [1,N1,N2], [2,N1,N2], [3,N1,N2] and so on.
Plus [N1,1,N2], [N1,2,N2], [N1,3,N3] and so on. So there is no need for
it to "stop at a certain list length", since it is never going to get
beyond a list length of three.

Matthew Huntbach

Relevant Pages

  • Re: abundance of irrationals!)
    ... No such "sum" exists except as, and only as, the limit of the infinite ... If an infinite sequence does not have to "achieve" its limit, ... > It is only for lists not initially known not to be surjective that ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... Not in that sum which stretches over all n. ... It is only for lists not initially known not to be surjective that ... "infinite" sequence. ... you cannot enumerate by them. ...
    (sci.math)
  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Simple recursive functions in Lisp
    ... (defun sum (list) ... (loop for x in list sum x)) ... Why is loop disqualified as "higher level"? ... use a macro such as RECURSE that has the same knowledge of lists and ...
    (comp.lang.lisp)
  • Re: Summing numbers from a list to a goal
    ... unique) that sum up to the goal sum plus or minus the acceptable ... Sort the lists of subset sums. ...
    (comp.programming.contests)
Loading