In article <·················@kochab> ·······@kochab.anu.oz.au (Dharmendra Sharma) writes:
>Given a sequence, I would like to generate its subsequences one at a
>time until some condition is met by a subsequence. Could someone please
>suggest how a function could be written in common lisp to do this.
I don't know how to "suggest" this other than to provide the code, since
it's so short. I hope I'm not doing someone's homework....
(defun generate-and-test (sequence predicate)
"Return a subsequence of SEQUENCE that satisfies PREDICATE.
Values are SUBSEQUENCE T if such a subsequence was found, NIL NIL otherwise."
(let ((length (length sequence)))
(dotimes (start length)
(do ((end (1+ start) (1+ end)))
((> end length) (values nil nil))
(let ((subsequence (subseq sequence start end)))
(when (funcall predicate subsequence)
(return subsequence t)))))))
The second value is necessary to handle the case where the satisfying
subsequence is () (since () is a sublist of all lists). This isn't as
efficient as it could be, as it tests the zero-length subsequence each time
through the outer loop. And it conses a lot of subsequences; an
interesting variant would be to require that the PREDICATE be a function
that accepts a sequence and :START and :END arguments, as most of the
built-in sequence functions do.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar