Path: utzoo!attcan!uunet!ncrlnk!ncrcae!hubcap!gatech!uflorida!ukma!mailrus!bcm!rice!kappa!gwydion
From: gwydion@kappa.rice.edu (Basalat Ali Raja)
Newsgroups: comp.lang.lisp
Subject: Re: permutations
Summary: One more solution to permutation
Message-ID: <2066@kalliope.rice.edu>
Date: 27 Oct 88 02:23:02 GMT
References: <1131@amelia.nas.nasa.gov> <14337@joyce.istc.sri.com>
Sender: usenet@rice.edu
Reply-To: gwydion@kappa.rice.edu (Basalat Ali Raja)
Organization: Rice University, Houston
Lines: 53

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