In article <··········@sparcserver.lrz-muenchen.de> ······@cis.uni-muenchen.de (Stephan Kepser) writes:
> In article <··················@michelv.aie.nl> ·····@michelv.aie.nl
> (Geert-Jan van Opdorp) writes:
> > In article <··········@spool.cs.wisc.edu> ··@brownie.cs.wisc.edu (Bryan
> So) writes:
> >
> >
> > This is somewhat shorter, but I paid no
> > attention to efficiency:
> >
> > (defun permute (l)
> > (if (null l) ; I don't like this. I suspect that there is a more
> > '(nil) ; natural way to make the function return '(nil) for nil.
> > (mapcan #'(lambda (e)
> > (mapcar #'(lambda (p) (cons e p))
> > (permute (remove e l))))
> > l)))
> >
> > Geert-Jan
> > --
> > Geert-Jan van Opdorp
>
>
> Interesting. This is 99.9% identical to the solution in PAIP (Paradigms of
> AI Programming, P. Norvig) p. 150, that Marty Hall points to.
Funny. Apparently this is an obvious way to implement it
in Lisp, but I think it is neither the most beautiful,
nor the most efficient implementation. It seems to me
an AI text book should do better!
>The very
> small difference is that Norvig uses the form
> (remove e l :count 1 :test #'eq)
> to remove the element from the list. Much later in the book (p. 680/682)
> it is explained, why the :test #'eq should be there: REMOVE uses EQL as
> standard test. And some elements in the list might be EQL without being
> EQ. If you then choose the second of those EQL elements, REMOVE will
> unfortunately remove the FIRST one, instead of the second. That's why you
> need EQ here to be sure to get the right one.
Also of course the #'eq and the #'count 1 add some
efficiency. Still a lot of duplicate lists are
produced. It can certainly be done much more efficient.
Can anybody come up with an implementation in
which no two equal (sub)list are produced? So the
result should contain no (sub)lists that are equal without
being eq.
Geert-Jan
--
Geert-Jan van Opdorp
AI-Engineering
Amsterdam, The Netherlands
·····@aie.nl