raible@orville.nas.nasa.gov (Eric L. Raible) (10/18/88)
(defun permutations (elements)
(if (null elements)
(list nil)
(mapcan
#'(lambda (element)
(mapcar
#'(lambda (permutation)
(cons element permutation))
(permutations (remove element elements))))
elements)))
Comments? Alternatives?miner@aai3.uucp (Stephen E. Miner) (10/19/88)
In article <1131@amelia.nas.nasa.gov> raible@orville.nas.nasa.gov (Eric L. Raible) writes: > >(defun permutations (elements) > (if (null elements) > (list nil) > (mapcan > #'(lambda (element) > (mapcar > #'(lambda (permutation) > (cons element permutation)) > (permutations (remove element elements)))) > elements))) > >Comments? Alternatives? Here's an alternative... (defun propagate (element perm) "Returns a list of 'propagations' of the ELEMENT through the list PERM." (propagate-aux element nil perm)) (defun propagate-aux (element before after) "Returns a list of lists each with the prefix BEFORE followed by one of the possible insertions of ELEMENT into the list AFTER." (if (endp after) (list (append before (list element))) (cons (append before (cons element after)) (propagate-aux element (append before (list (car after))) (cdr after))))) (defun permu-extend (element permu-list) "Returns an extended list of permutations by propagating the new ELEMENT through each of the base permutations in PERMU-LIST." (if (endp permu-list) nil (append (propagate element (car permu-list)) (permu-extend element (cdr permu-list))))) (defun permu (elements) "Returns a list of the permutations of the list ELEMENTS." (if (endp elements) (list nil) (permu-extend (car elements) (permu (cdr elements))))) Stephen E. Miner miner@sri.com *** My other computer is a Macintosh ***
jrc@ukc.ac.uk (J.R.G.Cupitt) (10/24/88)
In article <1131@amelia.nas.nasa.gov> raible@orville.nas.nasa.gov (Eric L. Raible) writes: }(defun permutations (elements) } (if (null elements) } (list nil) } (mapcan } #'(lambda (element) } (mapcar } #'(lambda (permutation) } (cons element permutation)) } (permutations (remove element elements)))) } elements))) } }Comments? Alternatives? Good grief! I almost collapsed when I saw this .. I realise that this is a LISP group, but I can't resist posting the same algorithm in Miranda: perms :: [*] -> [[*]] perms x = [[]], x = [] = [ a:p | a <- x; p <- perms (x--[a]) ], otherwise John Cupitt
alex@umbc3.UMD.EDU (Alex S. Crain) (10/26/88)
In article <5671@eagle.ukc.ac.uk> jrc@ukc.ac.uk (J.R.Cupitt) writes: [lisp code for permutations function deleted] >Good grief! I almost collapsed when I saw this .. I realise that this is a >LISP group, but I can't resist posting the same algorithm in Miranda: [miranda code for permutations function deleted] I don't understand the motive behind this. matrix multiplication is easier in Berkeley fp than it is in Lisp, but that doesn't make it a superior language. The permutation function is probably easy in APL too... I can understand the taunts from POPLOG users, in that POPLOG is all of CL plus an alternate interface (several in fact) and while I've never used POPLOG, it sounds like a nice extension package to CL, which could prove useful in certain situations. My understanding of Miranda, however, is that it is a purely functional language, and therefore not directly related to CL, which lost most of its function roots long ago. I would have liked to see alternative suggestions for the permutations function in lisp, and would have tried to offer some if I wasn't so busy right now. I don't care much for the map* functions, and am always looking at alternate styles to code mapping problems. "My language is better then your language" I really don't need. -- :alex. Systems Programmer nerwin!alex@umbc3.umd.edu UMBC alex@umbc3.umd.edu
johnson@csli.STANFORD.EDU (Mark Johnson) (10/26/88)
Here's an alternative definition of permute which avoids all use of
assignment operations. Note that the original definition of
permute in terms of mapping operations did this too. I much
prefer the original definition to the one I give below, but you said
you want to see alternatives, so here goes...
(Just in case you're wondering, this style of programming comes from
trying to write Lisp programs the same way you'd write a Prolog
program).
(defun permute (list)
(if list
(inserts (first list) (permute (rest list)))
'(()) ))
(defun inserts (elt lists)
(if lists
(append (if (null (first lists))
(list (list elt))
(cons (cons elt (first lists))
(prepends (first (first lists))
(inserts elt (list (rest (first lists)))))))
(inserts elt (rest lists)))
'() ))
(defun prepends (elt lists)
(if lists
(cons (cons elt (first lists))
(prepends elt (rest lists)))
'()))
#|
;;; Original definitions of inserts and prepends, from which the
definitions
;;; above are obtained by unfolding with respect to insert and append
respectively.
(defun inserts (elt lists)
(if lists
(append (insert elt (first lists))
(inserts elt (rest lists)))
'()))
(defun insert (elt list)
(if (null list)
(list (list elt))
(cons (cons elt list)
(prepends (first list)
(insert elt (rest list))))))
(defun prepends (elt lists)
(if lists
(cons (prepend elt (first lists))
(prepends elt (rest lists)))
'()))
(defun prepend (elt list)
(cons elt list))
|#gwydion@kappa.rice.edu (Basalat Ali Raja) (10/27/88)
nerwin!alex@umbc3.umd.edu writes > I would have liked to see alternative suggestions for the permutations >function in lisp, and would have tried to offer some if I wasn't so busy right >now. I don't care much for the map* functions, and am always looking at >alternate styles to code mapping problems. "My language is better then your >language" I really don't need. Here is one more solution to the permutations problem. (defun sub-perm (prev el after) (if (not (null? after)) (append (sprinkle el (permutation (append prev after))) (sub-perm (reverse (cons el (reverse prev))) (car after) (cdr after) ) ) () ) ) ; where sprinkle is defined as: (defun sprinkle (el plist) (mapcar (lambda (one-p) (cons el one-p)) plist) ) ; and the permutation function is, of course: (defun permutation (l) (if (null? l) () (sub-perm () (car l) (cdr l)) ) ) Please excuse my syntax; it's a Scheme programmer trying to write in plain Lisp (I am sure there is some version out there that can take this, somewhere.....) The code is not guaranteed; it's been a long time since I had need for this, but I think the general idea is correct. Summary of solution: Foreach element E in a list L to be permuted Permute L without E. Cons E to the beginning of each permuted list from the above result. Append all the sub-lists from the above together. Sincerely, gwydion@cleo.rice.edu