Hey everyone,
I've been toying with some lisp code to generate all combinations of a
given size from a set (represented as a list). I've come up with a few
variations that generate the whole list at once, and I'd like to write
a version that can hand off a single item at a time (i.e. a generating
function).
Here's my (recursive) function for the operation:
(defun f-comb-n (S n)
(labels ((rec (S1 S2)
(cond
((= (length S2) n) (list S2))
((null S1) nil)
(t (append (rec (cdr S1) (cons (car S1) S2))
(rec (cdr S1) S2))))))
(rec S ())))
and here's my macro version:
(defmacro m-comb-n (S n)
(labels ((comb-n-ator (set numb allsymbs)
(let ((mine (gensym)))
(cond
((= numb 0)
`(list (loop for ,mine in ,(cons 'list allsymbs)
collecting (car ,mine))))
(t
`(loop for ,mine on (cdr ,set)
nconcing
,(comb-n-ator mine (1- numb) (cons mine allsymbs))))))))
(let ((topsymb (gensym)))
`(loop for ,topsymb on ,S
nconcing
,(comb-n-ator topsymb (1- n) (list topsymb))))))
I'm a little surprised to find the function version noticeably faster
than the macro one, (and I wouldn't mind other's thoughts as to why
this is) and I'd like to know what you all think would be a reasonable
approach to a generating function version of one or both of these. I've
got some vague idea about a call-with-current-continuation thing, but I
don't really understand that too well.
Happy hacking!
Jason
P.S. I should probably mention that this is not a homework assignment;
I did my time already! I'm just playing with lisp in my spare time and
looking for illuminating advice from those more sage than I.
"jason" <···········@gmail.com> writes:
> Hey everyone,
>
> I've been toying with some lisp code to generate all combinations of a
> given size from a set (represented as a list). I've come up with a few
> variations that generate the whole list at once, and I'd like to write
> a version that can hand off a single item at a time (i.e. a generating
> function).
A CLOS based solution:
http://darcs.informatimago.com/local/darcs/public/lisp/common-lisp/combination.lisp
http://www.informatimago.com/develop/lisp/index.html
A good exercise would be to write it as a closure.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Klingon function calls do not have "parameters" -- they have
"arguments" and they ALWAYS WIN THEM."
"justinhj" <········@gmail.com> writes:
>>Pascal Bourguignon wrote:
>> A good exercise would be to write it as a closure.
>
> Do you mean as a continuation, or am I confused?
Common Lisp hasn't continuations.
With a closure, you'd do something like:
(defun make-combination-generator (p n)
(let ((state (initial-state p n)))
(lambda ()
(if (no-more-combination-p state)
nil
(prog1
(current-combination state)
(setf state (next-state state)))))))
Then you can write:
(loop
:with comb-gen = (make-combination-generator p n)
:for comb = (funcall comb-gen)
:while comb
:do (print comb))
for example.
--
__Pascal Bourguignon__ http://www.informatimago.com/
You're always typing.
Well, let's see you ignore my
sitting on your hands.
Pascal Bourguignon wrote:
> "justinhj" <········@gmail.com> writes:
>
> >>Pascal Bourguignon wrote:
> >> A good exercise would be to write it as a closure.
> >
> > Do you mean as a continuation, or am I confused?
>
> Common Lisp hasn't continuations.
No, but with closures it's not hard to add.
> With a closure, you'd do something like:
>
> (defun make-combination-generator (p n)
> (let ((state (initial-state p n)))
> (lambda ()
> (if (no-more-combination-p state)
> nil
> (prog1
> (current-combination state)
> (setf state (next-state state)))))))
>
> Then you can write:
>
> (loop
> :with comb-gen = (make-combination-generator p n)
> :for comb = (funcall comb-gen)
> :while comb
> :do (print comb))
>
> for example.
Gotcha.