The problem - all possible permutations of a list, eg (a b c d e) and to
generalize the function in a lisp like manner. My very unlisp like solution
is to use (no laughing now)
(setq factn (factorial (length lst))) as an index for the outer loop
driver. driving "factorial like" to the inner nodes with a loop and
successive n -1 indices [(setq n (length lst))]. (member (car node) lst))
keeps track of the nodes location in the orignal list and (set-difference
lst node) tells what is left. this algorithm makes alot of very
un-eleagant use of stored node semiphors to understand which node it is on.
[eq every (/ factn n) go back to top node and (setq next-node (list (car
top-node-lst) ) top-node-lst (cdr top-node-lst))]. I'm sure you get the
picture.
I wouldn't worry about it so much but I will be presenting this problem at a
seminar (solving real problems with the PC) for graduate students, so I
would like to have an elegant solution.
Thanks Rusty
In article <············@excalibur.flash.net>,
"rusty craine" <········@flash.net> wrote:
> The problem - all possible permutations of a list, eg (a b c d e) and to
> generalize the function in a lisp like manner.
I can't give an example in Lisp because of my current illiteracy. But The
thought of a tree springs to mind. Well, a list of trees. For each atom in
the list, make that the root node of a tree. Under that node, make each
remaining atom a child node. Now under each of those nodes, make all the
atoms not included in the line child nodes, and so on. The permutations
should be found by traversing the trees. I can't do ascii art too well, but
I'll try an example with 'a as the root of the first tree.
a
b c d e
cde bde bce bcd
de ce cd de be de ce be bc cd bd bc
e d e c d c e d e b e d e c e b c b d c d b c b
The depth of the recursion is the same as the number of items in the list.
Gee, I hope I did this right. If so, the same procedure applies to b, c, d,
&e. Anyway, this is a nice recursive algorithm if it is the correct one.
Just Lisp it!
David Steuber
The Interloper at work
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
NEVER MIND but thanks - I came up with a way that satisfies me. The top
level is still iteratetive using the (/ (factorial (length l) (length l)) as
the loop conditional. The second level is recursive each time passing the
current-node and a list the remaining elelments till no more elements
remain. geeez nothing to it when ya stop working so hard and start
thinking more. Say what you may about the philosophy of lisp....t'is a
thinking man's tool.
rusty
>
>
>
One elegant way of generating permutations (or any other form of combinatoric
enumeration) is to write a nondeterministic description of the combinatoric
structure. This can be done with Screamer, a nondeterministic extension to
Common Lisp.
(defun a-split-of-internal (x y)
(if (null? y)
(list x y)
(either (list x y)
(a-split-of-internal (append x (list (first y))) (rest y)))))
(defun a-split-of (l) (a-split-of-internal '() l))
(defun a-permutation-of (l)
(if (null l)
l
(let ((split (a-split-of (a-permutation-of (rest l)))))
(append (first split) (cons (first l) (second split))))))
(defun permutations-of (l) (all-values (a-permutation-of l)))
You can get Screamer from my home page.
Jeff (http://www.neci.nj.nec.com/homepages/qobi)
On 12 Oct 1998 10:29:35 -0400, Jeffrey Mark Siskind
<····@research.nj.nec.com> claimed or asked:
% One elegant way of generating permutations (or any other form of combinatoric
% enumeration) is to write a nondeterministic description of the combinatoric
% structure. This can be done with Screamer, a nondeterministic extension to
% Common Lisp.
Pardon my ignorance, but how can a single threaded algorithm be
nondeterministic?
--
David Steuber (ver 1.31.2a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.
So I have this chicken, see? And it hatched from this egg, see? But
the egg wasn't laid by a chicken. It was cross-laid by a turkey.
This probably depends on one's point of view, but from a certain
perspective it a choice of which branch to try next depended on, oh,
say, the number of milliseconds since startup mod, oh, say, 13 it would
be approximately non-deterministic.
In another sense it would be non-deterministic if it depended on the
last choices made by the user of the interface.
Of course these two choices could be combined. (But I don't know what
Mark Siskind ment by nondeterministic either. It just doesn't raise a
flag [throw an exception?]).
David Steuber The Interloper wrote:
>
> On 12 Oct 1998 10:29:35 -0400, Jeffrey Mark Siskind
> <····@research.nj.nec.com> claimed or asked:
>
> % One elegant way of generating permutations (or any other form of combinatoric
> % enumeration) is to write a nondeterministic description of the combinatoric
> % structure. This can be done with Screamer, a nondeterministic extension to
> % Common Lisp.
>
> Pardon my ignorance, but how can a single threaded algorithm be
> nondeterministic?
>
> --
> David Steuber (ver 1.31.2a)
> http://www.david-steuber.com
> To reply by e-mail, replace trashcan with david.
>
> So I have this chicken, see? And it hatched from this egg, see? But
> the egg wasn't laid by a chicken. It was cross-laid by a turkey.
In article <············@excalibur.flash.net>,
rusty craine <········@flash.net> wrote:
>The problem - all possible permutations of a list, eg (a b c d e) and to
>generalize the function in a lisp like manner. My very unlisp like solution
[...]
>I wouldn't worry about it so much but I will be presenting this problem at a
>seminar (solving real problems with the PC) for graduate students, so I
>would like to have an elegant solution.
Here is one way that is perhaps more lisp-like:
(defun list-permutations (list)
"Form list of permutations of items in given list."
(if (null list) '(())
(loop for i in list
append (mapcar #'(lambda (x) (cons i x))
(list-permutations (remove i list))))))
--
Dave Seaman ·······@purdue.edu
++++ stop the execution of Mumia Abu-Jamal ++++
++++ if you agree copy these lines to your sig ++++
++++ see http://www.xs4all.nl/~tank/spg-l/sigaction.htm ++++
This is Peter Norvig's permutation's code, from his excellent book,
Paradigms of Artificial Intelligence Programming
(http://www.norvig.com/paip.html).
(defun permutations (bag) "Return a list of all the permutations of the
input."
;; If the input is nil, there is only one permutation: ;; nil itself
(if (null bag) '(())
;; Otherwise, take an element, e, out of the bag.
;; Generate all permutations of the remaining elements,
;; And add e to the front of each of these.
;; Do this for all possible e to generate all permutations.
(mapcan #'(lambda (e) (mapcar #'(lambda (p) (cons e
p))
(permutations
(remove e bag :count 1 :test #'eq))))
bag)))
rusty craine wrote in message <············@excalibur.flash.net>...
>The problem - all possible permutations of a list, eg (a b c d e) and to
>generalize the function in a lisp like manner. My very unlisp like
solution
>is to use (no laughing now)
>(setq factn (factorial (length lst))) as an index for the outer loop
>driver. driving "factorial like" to the inner nodes with a loop and
>successive n -1 indices [(setq n (length lst))]. (member (car node) lst))
>keeps track of the nodes location in the orignal list and (set-difference
>lst node) tells what is left. this algorithm makes alot of very
>un-eleagant use of stored node semiphors to understand which node it is on.
>[eq every (/ factn n) go back to top node and (setq next-node (list (car
>top-node-lst) ) top-node-lst (cdr top-node-lst))]. I'm sure you get the
>picture.
>
>I wouldn't worry about it so much but I will be presenting this problem at
a
>seminar (solving real problems with the PC) for graduate students, so I
>would like to have an elegant solution.
>
>Thanks Rusty
>
>
>
>
In article <············@excalibur.flash.net>, "rusty craine"
<········@flash.net> wrote:
> The problem - all possible permutations of a list, eg (a b c d e) and to
> generalize the function in a lisp like manner. My very unlisp like solution
> is to use (no laughing now)
> (setq factn (factorial (length lst))) as an index for the outer loop
> driver. driving "factorial like" to the inner nodes with a loop and
> successive n -1 indices [(setq n (length lst))]. (member (car node) lst))
> keeps track of the nodes location in the orignal list and (set-difference
> lst node) tells what is left. this algorithm makes alot of very
> un-eleagant use of stored node semiphors to understand which node it is on.
> [eq every (/ factn n) go back to top node and (setq next-node (list (car
> top-node-lst) ) top-node-lst (cdr top-node-lst))]. I'm sure you get the
> picture.
>
> I wouldn't worry about it so much but I will be presenting this problem at a
> seminar (solving real problems with the PC) for graduate students, so I
> would like to have an elegant solution.
>
> Thanks Rusty
I wrote this about 8 or 9 years ago. -d
? (defun permute (x)
(if (cdr x)
(mapcon
#'(lambda (y)
(mapcar
#'(lambda (z) (cons (car y) z))
(permute (nconc (ldiff x y) (cdr y)))))
x)
(list x)))
PERMUTE
? (permute '(a b c))
((A B C) (A C B) (B A C) (B C A) (C A B) (C B A))
?
In article <····················@x066.bit-net.com>, ···@flavors.com (David
D. Smith) wrote:
> ? (defun permute (x)
> (if (cdr x)
> (mapcon
> #'(lambda (y)
> (mapcar
> #'(lambda (z) (cons (car y) z))
> (permute (nconc (ldiff x y) (cdr y)))))
> x)
> (list x)))
I have a macro I like to use called MAPLET that can make mapping code
easier to read. It combines the functionality of MAPCAR with the
easier-on-the-eyes syntax of LET. For example:
(maplet ( (x '(1 2 3)) ) (+ x 1)) => (2 3 4)
Here's the definition of MAPLET:
(defmacro maplet (bindings &body body)
`(mapcar #'(lambda ,(mapcar #'car bindings) ,@body)
,@(mapcar #'second bindings)))
There's also MAPPENDLET which does the same thing except using MAPCON
instead of MAPCAR.
Here's PERMUTE written using MAPLET:
(defun permute (list)
(if (null list)
;; Base case - there is one permutation of the empty list: itself
'(())
;; Otherwise, for every element in the list, append the results of...
(mappendlet ( (element list) )
;; ... generating the permutations of the list without that element...
(maplet ( (sub-permutation (permute (remove element list :count 1))) )
;; ... and consing the element on to each sub-permutation
(cons element sub-permutation)))))
I find this easier to read because it brings the variable being mapped
and the list it's being mapped over together in the code.
FWIW,
E.
···@jpl.nasa.gov (Erann Gat) writes:
(Hi, Erann!)
>I have a macro I like to use called MAPLET that can make mapping code
>easier to read. It combines the functionality of MAPCAR with the
>easier-on-the-eyes syntax of LET. For example:
>(maplet ( (x '(1 2 3)) ) (+ x 1)) => (2 3 4)
>There's also MAPPENDLET which does the same thing except using MAPCON
>instead of MAPCAR.
You see this kind of combination all the time in Common Lisp code,
only the writer often leaves out the function version of something and
goes straight for the macro -- an irritating habit to us Schemers. I
had an attempt at a general solution that went something like
(defmacro with (fun bindings &body body)
"Generalized LET macro."
`(,fun #'(lambda ,(mapcar #'first bindings)
,@body)
,@(mapcar #'second bindings)))
so that your example would go
(with mapcar ((x '(1 2 3))) (+ x 1))
>I find this easier to read because it brings the variable being mapped
>and the list it's being mapped over together in the code.
>FWIW,
>E.
--
Darius Bacon http://www.well.com/~djello
In article <············@its.hooked.net>, ······@well.com (Darius Bacon) wrote:
> (defmacro with (fun bindings &body body)
> "Generalized LET macro."
> `(,fun #'(lambda ,(mapcar #'first bindings)
> ,@body)
> ,@(mapcar #'second bindings)))
>
> so that your example would go
>
> (with mapcar ((x '(1 2 3))) (+ x 1))
Say, that's a pretty slick idea. You can also do things like:
(defun open-files (fn &rest filenames)
(let ( (files (mapcar #'open filenames)) )
(unwind-protect
(apply fn files)
(mapcar #'close files))))
(with open-files ( (f "file1") (g "file2") ) ...)
Maybe we can boil all CL macros and special forms down to one ur-macro! :-)
E.
···@jpl.nasa.gov (Erann Gat) writes:
>
> In article <············@its.hooked.net>, ······@well.com (Darius Bacon) wrote:
>
> > (defmacro with (fun bindings &body body)
> > "Generalized LET macro."
> > `(,fun #'(lambda ,(mapcar #'first bindings)
> > ,@body)
> > ,@(mapcar #'second bindings)))
> >
> > so that your example would go
> >
> > (with mapcar ((x '(1 2 3))) (+ x 1))
>
> Say, that's a pretty slick idea. You can also do things like:
>
> (defun open-files (fn &rest filenames)
> (let ( (files (mapcar #'open filenames)) )
> (unwind-protect
> (apply fn files)
> (mapcar #'close files))))
>
> (with open-files ( (f "file1") (g "file2") ) ...)
>
> Maybe we can boil all CL macros and special forms down to one ur-macro! :-)
This is a good example of a place where a general purpose macro would
break down because it would probably make the same coding error
that you made here.
Most WITH-OPEN-FILE implementations I've ever seen, ever since when
that macro was first invented in the late 1970's, having a timing
window during which they do not guarantee closure of the file.
Sometime when I'm not running out the door, ask me and I'll post a
note about how I think the language would have to be changed in order
to "guarantee" totally correct behavior. But to see the bug in yours,
which is subtle and you shouldn't feel to bad about missing, but
which is nevertheless important not to miss, consider what happens if
you get a file not found error for the open of file2 and you hit abort.
At the very least, you should do:
(defun open-files (fn &rest filenames)
(let ((files '()))
(unwind-protect (progn (dolist (file filenames) (push (open file) files))
(apply fn (reverse files)))
(mapcar #'close files))))
so that the files will hold the ones so far if you lose in the opens,
the most obvious place to lose. You might bogusly try to optimize out
the consing in the REVERSE call there, but at the risk that the system
surgery being done to do the NREVERSE would leave your cons cells
inconsistent if interrupted and you'd only close some of them. so if you
do an NREVERSE, you need it in a WITHOUT-INTERRUPTS.
I won't address the fact that your function doesn't allow you to pass
open options, since I assume you didn't bother try to do that.
For extra credit, though, spot the remaining timing error even after
starting with my repaired code.
Oh, and in the process don't lose track of my original point which is
that this is not a general pattern for composing mapping operations
because usually the state of "interrupt deflection" isn't so
critical.
* Sam Steingold wrote:
> In that case I suggest that you analyze the performance of the code you
> received. Others sent 3 functions, implementing the same algorithm in
> slightly different ways:
I'm not sure this is a convincing argument since this is an
exponential algorithm! It would probably be better to do a clever
version which returns a lazy list of all the permutations, or perhaps
some more complex lazy structure which you could walk down to find the
one you want (well, obviously not for permutations itself, but for
some similarly awful algorithm).
--tim
> I'm not sure this is a convincing argument since this is an
> exponential algorithm! It would probably be better to do a clever
> version which returns a lazy list of all the permutations,
This is precisely what that variant that I posted did. A-PERMUTATION-OF is a
nondeterministic procedure which lazily returns each permutation one by one.
The ALL-VALUES construct then gathers these lazily produced results into a
single list.
or perhaps
> some more complex lazy structure which you could walk down to find the
> one you want (well, obviously not for permutations itself, but for
> some similarly awful algorithm).
That is precisely what Screamer, as a tool, is intended for.
Jeff (http://www.neci.nj.nec.com/homepages/qobi)
Rusty Craine wrote:
>>I wouldn't worry about it so much but I will be presenting this problem at
a
>>seminar (solving real problems with the PC) for graduate students, so I
>>would like to have an elegant solution.
Thank you so much for your input. My presentation was this morning and
went very well due in great part from this news group's excellent input.
The presentation was to a group of OralMaxiallary surgery residents and
Fellows that do a great deal of research. As one would expect most of
their research has to do with quantifing various aesthetic relationships and
moving these relationships from an aesthete's view to mathematical view.
Seems like a good place for lisp. The Fellows usually end up at our
Hospital Information System after they have exhuasted the resources of SSPS.
Geeez some of their request are not so trivial.
Thanks again
rusty