combinations iterator
in [Lisp]
|
Prev: combinations not working
Next: bad-idea-p?
From: mark.hoemmen on 1 Jan 2007 16:11 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
From: Pascal Bourguignon on 1 Jan 2007 17:47 "mark.hoemmen(a)gmail.com" <mark.hoemmen(a)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."
From: mark.hoemmen on 2 Jan 2007 02:35 On Jan 1, 2:47 pm, Pascal Bourguignon <p...(a)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
From: Pascal Bourguignon on 2 Jan 2007 02:52 "mark.hoemmen(a)gmail.com" <mark.hoemmen(a)gmail.com> writes: > On Jan 1, 2:47 pm, Pascal Bourguignon <p...(a)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."
From: Steven E. Harris on 2 Jan 2007 12:02
"mark.hoemmen(a)gmail.com" <mark.hoemmen(a)gmail.com> writes: > 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. I wrote combination and permutation generators that use the "call-with-"-style interface: One provides a function to receive each fresh combination or permutation, which are generated one by one, avoiding the space explosion you describe. Such "call-with" functions may be trivially wrapped in "with-" or "do-" macros. Again, no iterator is exposed, but no intermediate results are built up either. ,----[ Combinations drawing 3 elements from a 5-element vector ] | (call-with-combinations #'print 3 (vector 1 2 3 4 5)) | | #(1 2 3) | #(1 2 4) | #(1 2 5) | #(1 3 4) | #(1 3 5) | #(1 4 5) | #(2 3 4) | #(2 3 5) | #(2 4 5) | #(3 4 5) `---- ,----[ Permutations drawing all elements from a 4-element vector ] | (call-with-permutations #'print (vector 4 3 2 1)) ... | | #(4 3 2 1) | #(3 4 2 1) | #(4 2 3 1) | #(2 4 3 1) | #(3 2 4 1) | #(2 3 4 1) | #(4 3 1 2) | #(3 4 1 2) | #(4 1 3 2) | #(1 4 3 2) | #(3 1 4 2) | #(1 3 4 2) | #(4 2 1 3) | #(2 4 1 3) | #(4 1 2 3) | #(1 4 2 3) | #(2 1 4 3) | #(1 2 4 3) | #(3 2 1 4) | #(2 3 1 4) | #(3 1 2 4) | #(1 3 2 4) | #(2 1 3 4) | #(1 2 3 4) `---- Let's add a "do-"-style wrapper: (defmacro do-permutations ((var vector) &body body) `(block nil (let ((.f. (lambda (,var) (declare (ignorable ,var)) ,@body))) (declare (dynamic-extent .f.)) (call-with-permutations .f. ,vector)))) ,----[ Using "do-"-style macro wrapper ] | (do-permutations (p (vector 4 3 2 1)) | (print p)) | | #(4 3 2 1) | #(3 4 2 1) | #(4 2 3 1) | #(2 4 3 1) | #(3 2 4 1) | #(2 3 4 1) | ... | | (do-permutations (p (vector 4 3 2 1)) | (when (= 1 (elt p 0)) | (return "Starts with 1."))) | "Starts with 1." `---- Let me know if you'd like to see the code. -- Steven E. Harris |