From: Bryan So
Subject: permutation
Date: 
Message-ID: <4em977$osl@spool.cs.wisc.edu>
I wonder if anyone has what they think is the simplest, shortest
implementation of "permutation" that can share with me.  e.g.,

   > (permute '(1 2 3))
   ((1 3 2) (3 1 2) (3 2 1) (1 2 3) (2 1 3) (2 3 1))

Mine is about 20 lines with 3 functions... really not clever.
Thanks.

Bryan
From: Peter Bengtson
Subject: Re: permutation
Date: 
Message-ID: <3115004B.512A@fst.se>
Marty Hall wrote:
> PAIP has an 8-line solution on page 150.

(NB: No sarcasm is intended in the following, merely mild amusement and 
a tongue firmly held in cheek:)

Thanks for this immensely useful information. I must say I'm thrilled. 
All that remains is to figure out what PAIP is (a book?) then find a 
bookshop carrying it, pay up, carry it home and turn to page 150. Maybe 
I'll like the algorithm. Who says the Internet doesn't make life easier?

Seriously, Marty, how about posting those 8 lines of code? I'd really 
like to see them!

Peter Bengtson
From: Marty Hall
Subject: Re: permutation
Date: 
Message-ID: <DMB35D.4u4@aplcenmp.apl.jhu.edu>
In article <·············@fst.se> Peter Bengtson <·····@fst.se> writes:
>Marty Hall wrote:
>> PAIP has an 8-line solution on page 150.
[...]
>Thanks for this immensely useful information. I must say I'm thrilled. 
>All that remains is to figure out what PAIP is (a book?) then find a 
>bookshop carrying it, pay up, carry it home and turn to page 150. Maybe 
>I'll like the algorithm. Who says the Internet doesn't make life easier?
>
>Seriously, Marty, how about posting those 8 lines of code? I'd really 
>like to see them!

OK, mea culpa! In a weak attempt at defense, all I can say is that I
consider PAIP a standard reference like CLtL, but I suppose it was
obvious that the person asking the question wasn't familiar with it
(or they wouldn't have asked :-).

PAIP: _Paradigms of AI Programming_, Peter Norvig. I posted the URL
for info on the text and the source code last week. IMHO the
definitive text on AI applications in Common Lisp and advanced CL in
general (although Graham's _On Lisp_ has better coverage of macros).

Here's the code from pg 150, minus the comments and doc string:

(defun permutations (bag)
  (if (null bag)
      '(())
      (mapcan #'(lambda (e)
		  (mapcar #'(lambda (p) (cons e p))
			  (permutations
			    (remove e bag :count 1 :test #'eq))))
	      bag)))

Cheers-
					- Marty
(proclaim '(inline skates))   
http://www.apl.jhu.edu/~hall/lisp.html
comp.lang.lisp / 1996 / jan