Greetings,
Back to my magic-square problem I have written something looking like
this :
(defun test-sum (sum lst)
;; returns (lst) if list element sum is equal to 'sum', NIL otherwise
(if (= (apply #'+ lst) sum)
(list lst)
()))
(defun sublist-n-elements-fixed-sum (n sum0 lst lst0)
(cond
((= n 0) (test-sum sum0 lst0))
(T
(setf acc NIL)
(dolist (x lst acc)
(cond
((<= x sum0)
(setf new-lst (remove x lst))
(setf new-lst0 (append (list x) lst0))
(setf val (sublist-n-elements-fixed-sum (1- n) sum0 new-lst
new-lst0))
(nconc acc (list val))
(print (append '("after call =>") (list val) (list acc)))
)
)
)
)
)
)
if called with:
(sublist-n-elements-fixed-sum 3 15 '(1 2 3 4 5 6 7 8 9) ())
it should return all lists of 3 elements from the list (1 2 3 4 5 6 7 8
9) and the sum of all elements in those list must be 15.
My biggest problem is in the recursive call :
(setf val (sublist-n-elements-fixed-sum (1- n) sum0 new-lst
new-lst0))
(nconc acc (list val))
(print (append '("after call =>") (list val) (list acc)))
I did a (trace ...) on the function and at some point the recursive
call returns a list, val is set to a good value but acc remains still
NIL at the print call which I really don't understand why. I used the
simplest example :
(print (sublist-n-elements-fixed-sum 2 3 '(1 2) ()))
and I get :
1: (SUBLIST-N-ELEMENTS-FIXED-SUM 2 3 (1 2) NIL)
2: (SUBLIST-N-ELEMENTS-FIXED-SUM 1 3 (2) (1))
3: (SUBLIST-N-ELEMENTS-FIXED-SUM 0 3 NIL (2 1))
3: returned ((2 1))
("after call =>" ((2 1)) NIL)
2: returned NIL
("after call =>" NIL NIL)
2: (SUBLIST-N-ELEMENTS-FIXED-SUM 1 3 (1) (2))
3: (SUBLIST-N-ELEMENTS-FIXED-SUM 0 3 NIL (1 2))
3: returned ((1 2))
("after call =>" ((1 2)) NIL)
2: returned NIL
("after call =>" NIL NIL)
1: returned NIL
NIL
Something is wrong here but I don't see why, I tried replacing (setf
acc ()) with (let ((acc ()) ...) but same result.
Any hints on what I might be doing wrong ?
Thanks,
Andrei
From: M Jared Finder
Subject: Re: Newbie lisper looking for hints
Date:
Message-ID: <4242f5cb_3@x-privat.org>
·······@mail.dntis.ro wrote:
> Greetings,
>
> Back to my magic-square problem I have written something looking like
> this :
>
> (defun test-sum (sum lst)
> ;; returns (lst) if list element sum is equal to 'sum', NIL otherwise
> (if (= (apply #'+ lst) sum)
> (list lst)
> ()))
>
>
> (defun sublist-n-elements-fixed-sum (n sum0 lst lst0)
> (cond
> ((= n 0) (test-sum sum0 lst0))
> (T
> (setf acc NIL)
> (dolist (x lst acc)
> (cond
> ((<= x sum0)
> (setf new-lst (remove x lst))
> (setf new-lst0 (append (list x) lst0))
> (setf val (sublist-n-elements-fixed-sum (1- n) sum0 new-lst
> new-lst0))
> (nconc acc (list val))
> (print (append '("after call =>") (list val) (list acc)))
> )
> )
> )
> )
> )
> )
>
>
>
> if called with:
> (sublist-n-elements-fixed-sum 3 15 '(1 2 3 4 5 6 7 8 9) ())
> it should return all lists of 3 elements from the list (1 2 3 4 5 6 7 8
> 9) and the sum of all elements in those list must be 15.
>
> My biggest problem is in the recursive call :
> (setf val (sublist-n-elements-fixed-sum (1- n) sum0 new-lst
> new-lst0))
> (nconc acc (list val))
> (print (append '("after call =>") (list val) (list acc)))
>
> I did a (trace ...) on the function and at some point the recursive
> call returns a list, val is set to a good value but acc remains still
> NIL at the print call which I really don't understand why. I used the
> simplest example :
>
> (print (sublist-n-elements-fixed-sum 2 3 '(1 2) ()))
>
> and I get :
>
> 1: (SUBLIST-N-ELEMENTS-FIXED-SUM 2 3 (1 2) NIL)
> 2: (SUBLIST-N-ELEMENTS-FIXED-SUM 1 3 (2) (1))
> 3: (SUBLIST-N-ELEMENTS-FIXED-SUM 0 3 NIL (2 1))
> 3: returned ((2 1))
>
> ("after call =>" ((2 1)) NIL)
> 2: returned NIL
>
> ("after call =>" NIL NIL)
> 2: (SUBLIST-N-ELEMENTS-FIXED-SUM 1 3 (1) (2))
> 3: (SUBLIST-N-ELEMENTS-FIXED-SUM 0 3 NIL (1 2))
> 3: returned ((1 2))
>
> ("after call =>" ((1 2)) NIL)
> 2: returned NIL
>
> ("after call =>" NIL NIL)
> 1: returned NIL
>
> NIL
>
>
> Something is wrong here but I don't see why, I tried replacing (setf
> acc ()) with (let ((acc ()) ...) but same result.
As an aside, you should replace all the SETF's with LET's, but that
doesn't appear to be causing the problem.
If you are using SBCL, I think this is a bug with its nconc. The
Hyperspec describes nconc as destructively concatenating all the lists
passed in, but this is not happenning. Replacing the (nconc acc ...)
with (setf acc (nconc acc ...)) fixes that. Here's a version of
sublist-n-elements-fixed-sum that works:
(defun sublist-n-elements-fixed-sum (n sum0 lst lst0)
(if (zerop n) (test-sum sum0 lst0)
(let ((acc nil))
(dolist (x lst acc)
(when (<= x sum0)
(setf acc (nconc acc (sublist-n-elements-fixed-sum (1- n)
sum0
(remove x lst)
(append (list x)
lst0)))))))))
Other comp.lang.lisp-ers, is this really a bug in SBCL (version
0.8.19.39), or is nconc not supposed to destructively modify the lists
passed in (as described in the Hyperspec)?
-- MJF
In article <··········@x-privat.org>,
M Jared Finder <·····@hpalace.com> wrote:
> If you are using SBCL, I think this is a bug with its nconc. The
> Hyperspec describes nconc as destructively concatenating all the lists
> passed in, but this is not happenning. Replacing the (nconc acc ...)
> with (setf acc (nconc acc ...)) fixes that. Here's a version of
> sublist-n-elements-fixed-sum that works:
It's not a bug in NCONC. Since his initial value of ACC is NIL, there's
nothing to destructively concatenate. NCONC can only perform
destructive concatenation if there's a cons to modify, and NIL isn't a
cons.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
·······@mail.dntis.ro writes:
> A-ha! Now that sounds like a good explanation of what happens, but then
> why does (setf acc (nconc acc val)) work ? Just curious ...
Because NCONC returns a value as well as possibly destructively
modifying ACC, and SETF alters the binding of ACC to that returned
value.
Christophe
In article <·······················@o13g2000cwo.googlegroups.com>,
·······@mail.dntis.ro wrote:
> A-ha! Now that sounds like a good explanation of what happens, but then
> why does (setf acc (nconc acc val)) work ? Just curious ...
Could you *please* quote the articles you're responding to, so we can
see the context.
In the new google interface, I believe it's in an Options menu or
something like that. Don't just click on the Reply button.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin wrote:
> In article <·······················@o13g2000cwo.googlegroups.com>,
> ·······@mail.dntis.ro wrote:
>
> > A-ha! Now that sounds like a good explanation of what happens, but
then
> > why does (setf acc (nconc acc val)) work ? Just curious ...
>
> Could you *please* quote the articles you're responding to, so we can
> see the context.
>
> In the new google interface, I believe it's in an Options menu or
> something like that. Don't just click on the Reply button.
Sorry, I thought google would put the reply as followup to the posts I
replied to.
Andrei
In article <·······················@z14g2000cwz.googlegroups.com>,
·······@mail.dntis.ro wrote:
> Barry Margolin wrote:
> > In article <·······················@o13g2000cwo.googlegroups.com>,
> > ·······@mail.dntis.ro wrote:
> >
> > > A-ha! Now that sounds like a good explanation of what happens, but
> then
> > > why does (setf acc (nconc acc val)) work ? Just curious ...
> >
> > Could you *please* quote the articles you're responding to, so we can
>
> > see the context.
> >
> > In the new google interface, I believe it's in an Options menu or
> > something like that. Don't just click on the Reply button.
>
> Sorry, I thought google would put the reply as followup to the posts I
> replied to.
It does. But quoting the relevant text that you're replying to is much
more polite than requiring everyone to find the referenced articles.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: M Jared Finder
Subject: Re: Newbie lisper looking for hints
Date:
Message-ID: <42482e53_3@x-privat.org>
Barry Margolin wrote:
> In article <··········@x-privat.org>,
> M Jared Finder <·····@hpalace.com> wrote:
>
>
>>If you are using SBCL, I think this is a bug with its nconc. The
>>Hyperspec describes nconc as destructively concatenating all the lists
>>passed in, but this is not happenning. Replacing the (nconc acc ...)
>>with (setf acc (nconc acc ...)) fixes that. Here's a version of
>>sublist-n-elements-fixed-sum that works:
>
> It's not a bug in NCONC. Since his initial value of ACC is NIL, there's
> nothing to destructively concatenate. NCONC can only perform
> destructive concatenation if there's a cons to modify, and NIL isn't a
> cons.
So it was a bug in my understanding of NCONC. I thought as much.
-- MJF
M Jared Finder <·····@hpalace.com> writes:
>
> So it was a bug in my understanding of NCONC. I thought as much.
>
As a general rule, the destructive list functions in Common Lisp are
ALLOWED to be destructive, but are NOT REQUIRED to be. The destructive
nature of the operation is seen as an opportunity for efficiency
optimizations rather than as being part of the contract of the
function. Accordingly, one should always assign the return value of any
such operation to the variable that you want to have that value.
It is perfectly conforming, for example, for a CL implementation to
really only implement REMOVE and APPEND and just use those functions as
the definitions of DELETE and NCONC as well. Normally this won't be
done, but it is legal.
But the real reason you want to do the assignment is that there are some
border cases where destructive modification is just not possible.
--
Thomas A. Russ, USC/Information Sciences Institute
In article <···············@sevak.isi.edu>,
> As a general rule, the destructive list functions in Common Lisp are
> ALLOWED to be destructive, but are NOT REQUIRED to be. The destructive
> nature of the operation is seen as an opportunity for efficiency
> optimizations rather than as being part of the contract of the
> function.
http://www.lispworks.com/documentation/HyperSpec/Body/f_nconc.htm
seems to imply that the nature of the list modification is specified
and required for NCONC's case.
> Accordingly, one should always assign the return value of any
> such operation to the variable that you want to have that value.
This is obviously still true, though.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
From: M Jared Finder
Subject: Re: Newbie lisper looking for hints
Date:
Message-ID: <424971e1_3@x-privat.org>
Brian Downing wrote:
> In article <···············@sevak.isi.edu>,
>
>>As a general rule, the destructive list functions in Common Lisp are
>>ALLOWED to be destructive, but are NOT REQUIRED to be. The destructive
>>nature of the operation is seen as an opportunity for efficiency
>>optimizations rather than as being part of the contract of the
>>function.
>
>
> http://www.lispworks.com/documentation/HyperSpec/Body/f_nconc.htm
>
> seems to imply that the nature of the list modification is specified
> and required for NCONC's case.
Yeah, that was what was confusing for me. The example given also invoke
undefined behavior by modifying the constant list (a b c).
-- MJF
Brian Downing wrote:
> In article <···············@sevak.isi.edu>,
>
>>As a general rule, the destructive list functions in Common Lisp are
>>ALLOWED to be destructive, but are NOT REQUIRED to be. The destructive
>>nature of the operation is seen as an opportunity for efficiency
>>optimizations rather than as being part of the contract of the
>>function.
>
>
> http://www.lispworks.com/documentation/HyperSpec/Body/f_nconc.htm
>
> seems to imply that the nature of the list modification is specified
> and required for NCONC's case.
Hmmm. That does seem to be the case, thanks for the correciton. The
standard defines the operation of NCONC in terms of the use of RPLACD.
But it also specifies that NIL values are skipped over, as they must be.
So the upshot is that variables that can be bound to NIL and used as
arguments to NCONC will not be modified if they happen to be NIL.
-Tom.
--
Thomas A. Russ, USC/Information Sciences Institute
In article <···············@sevak.isi.edu>,
···@sevak.isi.edu (Thomas A. Russ) wrote:
> So the upshot is that variables that can be bound to NIL and used as
> arguments to NCONC will not be modified if they happen to be NIL.
NCONC never modifies variable bindings at all. It modifies cons cells.
If anything references one of these cons cells, directly or indirectly,
the change will be apparent when you follow that reference.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Joe Marshall
Subject: Re: Newbie lisper looking for hints
Date:
Message-ID: <eke5qc45.fsf@ccs.neu.edu>
·······@mail.dntis.ro writes:
> My biggest problem is in the recursive call :
> (setf val (sublist-n-elements-fixed-sum (1- n) sum0 new-lst
> new-lst0))
Where is VAL defined? You shouldn't just perform assignments to
undeclared variables!
I was under the impression that when you use setf you also declare that
variable and that it can be used in a recursive function. Now I see
that this might have some problems ...
·······@mail.dntis.ro writes:
> Greetings,
>
> Back to my magic-square problem I have written something looking like
> this :
>
> (defun test-sum (sum lst)
> ;; returns (lst) if list element sum is equal to 'sum', NIL otherwise
> (if (= (apply #'+ lst) sum)
> (list lst)
> ()))
>
>
> (defun sublist-n-elements-fixed-sum (n sum0 lst lst0)
> (cond
> ((= n 0) (test-sum sum0 lst0))
> (T
> (setf acc NIL)
> (dolist (x lst acc)
> (cond
> ((<= x sum0)
> (setf new-lst (remove x lst))
> (setf new-lst0 (append (list x) lst0))
> (setf val (sublist-n-elements-fixed-sum (1- n) sum0 new-lst
> new-lst0))
> (nconc acc (list val))
> (print (append '("after call =>") (list val) (list acc)))
> )
> )
> )
> )
> )
> )
>
>
>
Hi Andrei,
There are many problems with your code, from the fairly superficial (your
indentation style makes it hard to read), to much deeper ones: for example, you
are setf'ing new-lst, but this is not bound anywhere.
Additionally, from a design point of view your approach is unnatural, and
tightly coupled to your problem. I'm going to back up a little and from your
problem description below offer another approach.
> if called with:
> (sublist-n-elements-fixed-sum 3 15 '(1 2 3 4 5 6 7 8 9) ())
> it should return all lists of 3 elements from the list (1 2 3 4 5 6 7 8
> 9) and the sum of all elements in those list must be 15.
>
lets put these words into a functional form
(defun find-combinations-summing-to (sum length list)
(loop for x in (combinations length list)
when (= (sum-of-list x) sum) collect x))
Ok, that looks like what you want, the only problem is that we don't have
functions called combinations or sum-of-list....
lets solve the easy one first:
(defun sum-of-list (list)
(loop for x in list summing x))
Now we could have just put the loop code in find-combinations... but this is a
nice descriptive function, and much more generally useful than your test-sum
would be.
You were right that a recursive solutions to getting the n choose k
combinations out of a list can be nice, but your approach is likely what
confused you.
We are going to build up combinations by picking off pieces of the original list
and consing them up with shorter combinations:
(defun combinations (length list)
(if (= length 1)
(mapcar #'list list)
(append (mapcar (lambda (x) (cons (car list) x))
(combinations (1- length) (cdr list)))
(when (>= (length list) 2) (combinations length (cdr list))))))
This style may not be familiar to you, but avoids all the problems you ran into
with extra variables, etc.
the base case is when you want all possible length on entries turned into
length 1 lists.
e.g. (1 2 3) -> ((1) (2) (3))
otherwise, we pick off the first member of the list, and then cons it up with
every combination of length -1. When the sublist is long enough, we also must
collect the combinations of length that didn't include our first element.
CL-USER> (find-combinations-summing-to 15 3 (list 1 2 3 4 5 6 7 8 9))
((1 5 9) (1 6 8) (2 4 9) (2 5 8) (2 6 7) (3 4 8) (3 5 7) (4 5 6))
CL-USER>
Hope that helps! By the way, I just wrote this out in a straightforward way,
I suspect there improvements to be made
Simon.
Following my own post, sorry.
I should have noted that combinatorial functions like this can run out of memory
quickly --- if you have larger lists to deal with, we should probably look at a
version that does not cons up all combinations first and then evaluate them!
Simon
Thanks for the nice clear code, it looks like what I was searching for
- but coming from non-functional languages I still have to adjust my
mental structures to the lisp way. Point taken about indentations too
...
Andrei