* Re: Need help in understanding an example of recursion
[not found] <mailman.1503.1180804721.32220.help-gnu-emacs@gnu.org>
@ 2007-06-02 20:02 ` Pascal Bourguignon
2007-06-02 21:11 ` Nikos Apostolakis
0 siblings, 1 reply; 3+ messages in thread
From: Pascal Bourguignon @ 2007-06-02 20:02 UTC (permalink / raw)
To: help-gnu-emacs
Nikos Apostolakis <nikos.ap@gmail.com> writes:
> Hello group,
>
> I was browsing the source code of SAGE, and I tried to implement in
> elisp the function that computes all the partitions of an integer n.
> So I did the following:
>
> (defun nea-partitions (n)
> "Return a list with all partitions of the integer n."
> (if (= n 0)
> '(nil)
> (nea-next-partitions (nea-partitions (- n 1)))))
>
> (defun nea-next-partitions (lst)
> (append (mapcar (lambda (x) (cons 1 x)) lst)
> (dolist (elt (reverse lst) value)
> (when (and elt
> (or (= (length elt) 1)
> (> (car elt) (cadr elt))))
> (setq value (cons (cons (1+ (car elt)) (cdr elt))
> value))))))
>
> But this doesn't work:
Of course.
> (nea-partitions 0)
> => (nil)
> (nea-partitions 1)
> => ((1))
> (nea-partitions 2)
> => ((1 1) (2))
> (nea-partitions 3)
> => (1 1 1) (1 2) (3) (2))
> (nea-next-partitions '((1 1) (2)))
> => ((1 1 1) (1 2) (3))
> (nea-next-partitions (nea-partitions 2))
> => ((1 1 1) (1 2) (3) (2))
>
> Is there some subtle[0] point about recursion that I am missing?
> Any help in understanding this will be greatly appreciated.
This is not a question of recursion. It's a question of something you
should have learned the first day of your first programming course,
that you should not use global variables and you should initialize
your variables!
Your variable named value is not a local variable of
nea-next-partition. Moreover, value is a variable that's bound to
new values automatically, read it's documentation. C-h v value RET
To get your own variable named value, you must introduce it with let:
(defun nea-next-partitions (lst)
(append (mapcar (lambda (x) (cons 1 x)) lst)
(let ((value '()))
(dolist (elt (reverse lst) value)
(when (and elt
(or (= (length elt) 1)
(> (car elt) (cadr elt))))
(setq value (cons (cons (1+ (car elt)) (cdr elt))
value)))))))
Instead of writting (setq v (cons item v)), you could use push:
(require 'cl)
(defun nea-next-partitions (list)
(append (mapcar (lambda (x) (cons 1 x)) list)
(let ((value '()))
(dolist (element (reverse list) value)
(when (and element
(or (= (length element) 1)
(> (car element) (cadr element))))
(push (cons (1+ (car element)) (cdr element)) value))))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Need help in understanding an example of recursion
2007-06-02 20:02 ` Need help in understanding an example of recursion Pascal Bourguignon
@ 2007-06-02 21:11 ` Nikos Apostolakis
0 siblings, 0 replies; 3+ messages in thread
From: Nikos Apostolakis @ 2007-06-02 21:11 UTC (permalink / raw)
To: help-gnu-emacs
Pascal Bourguignon <pjb@informatimago.com> writes:
> Nikos Apostolakis <nikos.ap@gmail.com> writes:
>> Is there some subtle[0] point about recursion that I am missing?
>> Any help in understanding this will be greatly appreciated.
>
> This is not a question of recursion. It's a question of something you
> should have learned the first day of your first programming course,
> that you should not use global variables and you should initialize
> your variables!
>
>
> Your variable named value is not a local variable of
> nea-next-partition. Moreover, value is a variable that's bound to
> new values automatically, read it's documentation. C-h v value RET
>
This is embarasing. I actually red the documentation, and I
thought that in the dolist construction the third argument is
automatically local. Not sure where I got the impression since
the example in the manual does initialize the variable!
Thanks for the answer and the tips,
Nikos
^ permalink raw reply [flat|nested] 3+ messages in thread
* Need help in understanding an example of recursion
@ 2007-06-02 16:09 Nikos Apostolakis
0 siblings, 0 replies; 3+ messages in thread
From: Nikos Apostolakis @ 2007-06-02 16:09 UTC (permalink / raw)
To: help-gnu-emacs
Hello group,
I was browsing the source code of SAGE, and I tried to implement in
elisp the function that computes all the partitions of an integer n.
So I did the following:
(defun nea-partitions (n)
"Return a list with all partitions of the integer n."
(if (= n 0)
'(nil)
(nea-next-partitions (nea-partitions (- n 1)))))
(defun nea-next-partitions (lst)
(append (mapcar (lambda (x) (cons 1 x)) lst)
(dolist (elt (reverse lst) value)
(when (and elt
(or (= (length elt) 1)
(> (car elt) (cadr elt))))
(setq value (cons (cons (1+ (car elt)) (cdr elt))
value))))))
But this doesn't work:
(nea-partitions 0)
=> (nil)
(nea-partitions 1)
=> ((1))
(nea-partitions 2)
=> ((1 1) (2))
(nea-partitions 3)
=> (1 1 1) (1 2) (3) (2))
(nea-next-partitions '((1 1) (2)))
=> ((1 1 1) (1 2) (3))
(nea-next-partitions (nea-partitions 2))
=> ((1 1 1) (1 2) (3) (2))
Is there some subtle[0] point about recursion that I am missing?
Any help in understanding this will be greatly appreciated.
TIA,
Nikos
[0] for my level of understanding at least.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2007-06-02 21:11 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <mailman.1503.1180804721.32220.help-gnu-emacs@gnu.org>
2007-06-02 20:02 ` Need help in understanding an example of recursion Pascal Bourguignon
2007-06-02 21:11 ` Nikos Apostolakis
2007-06-02 16:09 Nikos Apostolakis
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.