Path: utzoo!yunexus!geac!syntron!jtsv16!uunet!seismo!sundc!pitstop!sun!decwrl!labrea!csli!johnson
From: johnson@csli.STANFORD.EDU (Mark Johnson)
Newsgroups: comp.lang.lisp
Subject: Re: permutations
Message-ID: <6139@csli.STANFORD.EDU>
Date: 26 Oct 88 14:17:07 GMT
Article-I.D.: csli.6139
References: <1131@amelia.nas.nasa.gov> <5671@eagle.ukc.ac.uk> <1295@umbc3.UMD.EDU>
Reply-To: johnson@csli.UUCP (Mark Johnson)
Organization: Center for the Study of Language and Information, Stanford U.
Lines: 62

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))

|#