Greetings!
I'd like an iterator over all the combinations of the elements of a set
(stored as, say, a list). I know the recursive definition of the set
of all combinations of a set, but I'd like to avoid the combinatorial
space explosion of actually _constructing_ the set of all combinations.
Is there an easy way of defining such an iterator using, say,
continuations?
Can this idea be extended, say via a macro, so that I can automatically
transform any process that creates successive data from one or more
data into an iterator?
mfh
············@gmail.com wrote:
> Greetings!
>
> I'd like an iterator over all the combinations of the elements of a set
> (stored as, say, a list). I know the recursive definition of the set
> of all combinations of a set, but I'd like to avoid the combinatorial
> space explosion of actually _constructing_ the set of all combinations.
>
>
> Is there an easy way of defining such an iterator using, say,
> continuations?
>
This suggests how to express the iteration position as an integer:
(defun all-combos (list)
(loop for combo-mask upfrom 1 below (expt 2 (length list))
do (print (loop for e-bit = 1 then (ash e-bit 1)
for e in list
when (logtest e-bit combo-mask)
collect e))))
A continuable iterator (left as an exercise) is just a closure over a
combo-mask variable initialized to zero and incremented on each call. (I
just made that last bit up without thinking too hard.)
> Can this idea be extended, say via a macro, so that I can automatically
> transform any process that creates successive data from one or more
> data into an iterator?
Sorry, I just took the low-hanging combinations fruit.
hth,kt
--
The Dalai Lama gets the same crap all the time.
-- Kenny Tilton on c.l.l when accused of immodesty
·············@gmail.com" <············@gmail.com> writes:
> Greetings!
>
> I'd like an iterator over all the combinations of the elements of a set
> (stored as, say, a list). I know the recursive definition of the set
> of all combinations of a set, but I'd like to avoid the combinatorial
> space explosion of actually _constructing_ the set of all combinations.
>
>
> Is there an easy way of defining such an iterator using, say,
> continuations?
>
> Can this idea be extended, say via a macro, so that I can automatically
> transform any process that creates successive data from one or more
> data into an iterator?
http://darcs.informatimago.com/darcs/public/lisp/common-lisp/combination.lisp
--
__Pascal Bourguignon__ http://www.informatimago.com/
"What is this talk of "release"? Klingons do not make software
"releases". Our software "escapes" leaving a bloody trail of
designers and quality assurance people in its wake."
On Jan 1, 2:47 pm, Pascal Bourguignon <····@informatimago.com> wrote:
> http://darcs.informatimago.com/darcs/public/lisp/common-lisp/combinat...
what i was thinking of for the second question (generalizing the idea
of iterator over a process) was something like this. If you want a
list of all the combinations of the elements of a given list, you do
something like this:
(defun combinations (list)
(cond ((null list) nil)
((atom list) (combinations (list list)))
((null (cdr list)) (cons list nil))
(t (append (cons (first list) (combinations (cdr list)))
(combinations (cdr list))))))
However, to get an iterator over the output list without actually
constructing the output list, we need some new operators. Suppose
(YIELD x) means "the value x should pop up the chain of YIELDs back to
the iterator, and when the chain ends, the result should be returned
now by the iterator," and (SEQ x y z ...) means "the iterator should
follow the sequence x, y, z if x, y, z, etc. YIELD something." Then we
could write:
(defun combinations (list)
(cond ((null list) (yield nil))
((atom list) (yield (combinations (list list))))
((null (cdr list))
(seq (yield list) (yield nil)))
(t (seq (yield (cons (first list) (combinations (cdr
list))))
(yield (combinations (cdr list)))))))
well, something like that; I'm not being very precise. The idea is
that you just write your algorithms like you would before, but instead
of collecting data into a data structure, you YIELD each datum as you
generate it. I know the SERIES package has something vaguely like the
YIELD operator; could it be (efficiently) adapted to the above case?
Or is this a job for continuations?
mfh
·············@gmail.com" <············@gmail.com> writes:
> On Jan 1, 2:47 pm, Pascal Bourguignon <····@informatimago.com> wrote:
>> http://darcs.informatimago.com/darcs/public/lisp/common-lisp/combinat...
>
> what i was thinking of for the second question (generalizing the idea
> of iterator over a process) was something like this. If you want a
> list of all the combinations of the elements of a given list, you do
> something like this:
>
> (defun combinations (list)
> (cond ((null list) nil)
> ((atom list) (combinations (list list)))
> ((null (cdr list)) (cons list nil))
> (t (append (cons (first list) (combinations (cdr list)))
> (combinations (cdr list))))))
>
> However, to get an iterator over the output list without actually
> constructing the output list, we need some new operators. Suppose
> (YIELD x) means "the value x should pop up the chain of YIELDs back to
> the iterator, and when the chain ends, the result should be returned
> now by the iterator," and (SEQ x y z ...) means "the iterator should
> follow the sequence x, y, z if x, y, z, etc. YIELD something." Then we
> could write:
>
> (defun combinations (list)
> (cond ((null list) (yield nil))
> ((atom list) (yield (combinations (list list))))
> ((null (cdr list))
> (seq (yield list) (yield nil)))
> (t (seq (yield (cons (first list) (combinations (cdr
> list))))
> (yield (combinations (cdr list)))))))
>
> well, something like that; I'm not being very precise. The idea is
> that you just write your algorithms like you would before, but instead
> of collecting data into a data structure, you YIELD each datum as you
> generate it. I know the SERIES package has something vaguely like the
> YIELD operator; could it be (efficiently) adapted to the above case?
> Or is this a job for continuations?
Yes, continuations, or coroutines. It's possible that partial
continuations we can implement in CL would be enough for this.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"What is this talk of "release"? Klingons do not make software
"releases". Our software "escapes" leaving a bloody trail of
designers and quality assurance people in its wake."
* "mark.hoemmen <·······················@48g2000cwx.XXXXXX.com>
| what i was thinking of for the second question (generalizing the idea
| of iterator over a process) was something like this. If you want a
| list of all the combinations of the elements of a given list, you do
| something like this:
|
| (defun combinations (list)
| (cond ((null list) nil)
| ((atom list) (combinations (list list)))
| ((null (cdr list)) (cons list nil))
| (t (append (cons (first list) (combinations (cdr list)))
| (combinations (cdr list))))))
Note This algorithm is wrong
(combinations (list 1 2 3)) ;; => (1 2 (3) (3) 2 (3) (3))
| However, to get an iterator over the output list without actually
| constructing the output list,
For solutions that do not construct the output list, See the
algorithms outlined in
news:<················@newsfe11.lga>
news:<··············@robolove.meer.net>
I should stress this is the preferable route to go.
| we need some new operators. Suppose (YIELD x) means "the value x
| should pop up the chain of YIELDs back to the iterator, and when the
| chain ends, the result should be returned now by the iterator," and
| (SEQ x y z ...) means "the iterator should follow the sequence x, y,
| z if x, y, z, etc. YIELD something." Then we could write:
[...]
| well, something like that; I'm not being very precise. The idea is
| that you just write your algorithms like you would before, but instead
| of collecting data into a data structure, you YIELD each datum as you
| generate it. I know the SERIES package has something vaguely like the
| YIELD operator; could it be (efficiently) adapted to the above case?
| Or is this a job for continuations?
As pjb suggested, this is indeed possible with simple continuations,
but without much advantage, in this example. To outline the
procedure using the condition system...
First We fix your function to work correctly:
(defun COMBINATIONS (list)
"Returns a list of all combinations elements of list LIST"
(cond ((endp list) (list nil))
(t (let ((remaining (COMBINATIONS (cdr list))))
(nconc remaining
(mapcar (lambda (c) (cons (car list) c))
remaining))))))
Next, rewrite this function using the suggested abstraction name:
YIELD. Everytime a value is computed it is YIELDed. Since the
explicit LIST has to be constructed anyway, in this case, we avoid
using SEQ.
(defun COMBINATIONS (list)
"VERSION-0-1"
(cond ((endp list) (LIST (YIELD nil)))
(t (let ((remaining (COMBINATIONS (cdr list))))
(NCONC remaining
(mapcar (lambda (c)
(YIELD (cons (car list) c)))
remaining))))))
Next, have YIELD signal a common lisp condition.
(define-condition yield (condition)
((value :initarg :value :reader yield-value))
(:report (lambda (condition stream)
(format stream "Yield Value: ~S" (yield-value condition)))))
(defun YIELD (X)
(cerror "Continue" 'yield :value X)
X)
Try it: This will drop you into the debugger. Choose the CONTINUE
restart to proceed.. This should yield each value in turn.
(combinations (list 1 2 3))
We avoided SEQ, but to demonstrate control flow consider the
following function.
(defun map-combinations (f list)
"Call F in turn on EACH COMBINATION OF LIST in some ORDER. Returns NIL."
(handler-bind ((yield
(lambda (c)
(funcall f (yield-value c))
(invoke-restart 'continue))))
(combinations list))
(values NIL))
(map-combinations (lambda (x) (format t "~A~%" X)) (list 1 2 3))
--
Madhu
(message (Hello ·············@gmail.com)
(you :wrote :on '(1 Jan 2007 13:11:15 -0800))
(
mh> I'd like an iterator over all the combinations of the elements of a set
mh> (stored as, say, a list).
why do you need that, did you program C++ or Python before?
you can easily create mapcar-style function, say mapcomb, that takes closure
as parameter and passes each combination to it.
if you don't like that syntatically, you can then wrap that in a macro
docomb that will create a lambda for you.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
Alex Mizrahi wrote:
> (message (Hello ·············@gmail.com)
> (you :wrote :on '(1 Jan 2007 13:11:15 -0800))
> (
>
> mh> I'd like an iterator over all the combinations of the elements of a set
> mh> (stored as, say, a list).
>
> why do you need that, did you program C++ or Python before?
d00d, dare you question my Lisp skillz?!? ;P
Seriously, see Paul Graham, "On Lisp," Ch. 20. Iterators are useful
where performing iterations over multiple data structures at the same
time. Imagine that you have three trees with the same structure, and
you want to combine data from the corresponding nodes of the first two
trees and store it in the corresponding node of the third tree. This
is _way_ easier with iterators, no? Otherwise you have to define a
mapcar-style function that can handle any number of data structures and
map over all of them at the same time. That sounds painful, at least
to me.
Personal note: I do admit that my first paid coding job was for a
semi-academic house that produced mostly C++, but it's (thankfully)
been a long time since I've coded any C++. I hack a lot of Matlab
nowadays but write a lot of utilities in CL.
mfh
(message (Hello ·············@gmail.com)
(you :wrote :on '(3 Jan 2007 12:32:23 -0800))
(
mh> Seriously, see Paul Graham, "On Lisp," Ch. 20. Iterators are useful
mh> where performing iterations over multiple data structures at the same
mh> time. Imagine that you have three trees with the same structure, and
mh> you want to combine data from the corresponding nodes of the first two
mh> trees and store it in the corresponding node of the third tree. This
mh> is _way_ easier with iterators, no?
hm, maybe..
although following article says that it's better to do it without iterators,
and shows how:
http://home.pipeline.com/~hbaker1/Iterator.html
mh> Otherwise you have to define a mapcar-style function that can handle
mh> any number of data structures and map over all of them at the same
mh> time. That sounds painful, at least to me.
aforementioned article shows how to iterate two trees simultaneously in
strictly functional manner -- using lambdas, of course. i wouldn't say it
looks very easy :)
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")