From: Grant Henderson
Subject: Permutations
Date: 
Message-ID: <8on46.9648$T65.638088@news3.cableinet.net>
Has anybody got any algorithms or code that works out all the
permutations for a given set {1n,2n,.......Nn}

Anything would be great
Cheers
Grant

From: glauber
Subject: Re: Permutations
Date: 
Message-ID: <92t37f$6ov$1@nnrp1.deja.com>
In article <·····················@news3.cableinet.net>,
  "Grant Henderson" <·········@cableinet.co.uk> wrote:
> Has anybody got any algorithms or code that works out all the
> permutations for a given set {1n,2n,.......Nn}


I asked this here a while ago and got a lot of interesting responses,
including code.

See if this URL works for you:
http://www.deja.com/viewthread.xp?AN=674042477&group=comp.lang.lisp

--
Glauber Ribeiro
··········@my-deja.com    http://www.myvehiclehistoryreport.com
"Opinions stated are my own and not representative of Experian"


Sent via Deja.com
http://www.deja.com/
From: Jochen Schmidt
Subject: Re: Permutations
Date: 
Message-ID: <92tciu$89l0p$1@ID-22205.news.dfncis.de>
glauber wrote:

> In article <·····················@news3.cableinet.net>,
>   "Grant Henderson" <·········@cableinet.co.uk> wrote:
>> Has anybody got any algorithms or code that works out all the
>> permutations for a given set {1n,2n,.......Nn}
> 
> 
> I asked this here a while ago and got a lot of interesting responses,
> including code.
> 
> See if this URL works for you:
> http://www.deja.com/viewthread.xp?AN=674042477&group=comp.lang.lisp

A chum of me just implemented a permutation function that works in constant 
space by only swapping in a fixed array without any copying. I've taken a 
look at it and it's seems to be rather impressive. It's not written in CL 
but in Pascal but it should be easy portable.
I'll ask him next time I see him.

Regards,
Jochen
From: Joe Marshall
Subject: Re: Permutations
Date: 
Message-ID: <g0j1u051.fsf@content-integrity.com>
Jochen Schmidt <···@dataheaven.de> writes:

> A chum of me just implemented a permutation function that works in constant 
> space by only swapping in a fixed array without any copying. I've taken a 
> look at it and it's seems to be rather impressive. It's not written in CL 
> but in Pascal but it should be easy portable.

Amazing what people will do when they don't have a garbage collector.


-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----
From: glauber
Subject: Re: Permutations
Date: 
Message-ID: <92tlqv$nv3$1@nnrp1.deja.com>
In article <············@content-integrity.com>,
  Joe Marshall <···@content-integrity.com> wrote:
> Jochen Schmidt <···@dataheaven.de> writes:
>
> > A chum of me just implemented a permutation function that works in constant
> > space by only swapping in a fixed array without any copying. I've taken a
> > look at it and it's seems to be rather impressive. It's not written in CL
> > but in Pascal but it should be easy portable.
>
> Amazing what people will do when they don't have a garbage collector.


One problem with permutations is that the usual recursive implementation
generates a lot of garbage that's not collectable until all permutations are
generated, and you run out of space this way.

glauber

--
Glauber Ribeiro
··········@my-deja.com    http://www.myvehiclehistoryreport.com
"Opinions stated are my own and not representative of Experian"


Sent via Deja.com
http://www.deja.com/
From: Johan Kullstam
Subject: Re: Permutations
Date: 
Message-ID: <m2n1d9bm4n.fsf@euler.axel.nom>
Jochen Schmidt <···@dataheaven.de> writes:

> glauber wrote:
> 
> > In article <·····················@news3.cableinet.net>,
> >   "Grant Henderson" <·········@cableinet.co.uk> wrote:
> >> Has anybody got any algorithms or code that works out all the
> >> permutations for a given set {1n,2n,.......Nn}
> > 
> > 
> > I asked this here a while ago and got a lot of interesting responses,
> > including code.
> > 
> > See if this URL works for you:
> > http://www.deja.com/viewthread.xp?AN=674042477&group=comp.lang.lisp
> 
> A chum of me just implemented a permutation function that works in constant 
> space by only swapping in a fixed array without any copying. I've taken a 
> look at it and it's seems to be rather impressive. It's not written in CL 
> but in Pascal but it should be easy portable.
> I'll ask him next time I see him.

this isn't all that hard if you look at it right.

consider this --

you have an array of N items A and an empty array B of N places.

take one item (at random) from A, say for the sake of argment, it's
element 14.  put it in B.

you don't want to take this item again.  you could mark this item as
taken by writing a special token there.  however, you could just copy
the 1st element into element 14 and let the new A be elements 2
through N.

take another item from 2 to N from A.  let it be 27.  copy A[27] to
B[2].  copy A[2] to A[27].

take an item from 3 to N...

notice that B never holds more than one more element than you've taken
from A.

implement this by using the dead part of A (the initial bit which
you've moved upwards the elements you've claimed) to store B.

thus you iterate upwards through the array and swap the I-th element
with a random one takes from I through N inclusive (sometimes you
"swap" with itself).

hope this helps.

-- 
J o h a n  K u l l s t a m
[········@ne.mediaone.net]
Don't Fear the Penguin!
From: Jochen Schmidt
Subject: Re: Permutations
Date: 
Message-ID: <92u36v$87mko$1@ID-22205.news.dfncis.de>
Johan Kullstam wrote:

> Jochen Schmidt <···@dataheaven.de> writes:
> 
>> glauber wrote:
>> 
>> > In article <·····················@news3.cableinet.net>,
>> >   "Grant Henderson" <·········@cableinet.co.uk> wrote:
>> >> Has anybody got any algorithms or code that works out all the
>> >> permutations for a given set {1n,2n,.......Nn}
>> > 
>> > 
>> > I asked this here a while ago and got a lot of interesting responses,
>> > including code.
>> > 
>> > See if this URL works for you:
>> > http://www.deja.com/viewthread.xp?AN=674042477&group=comp.lang.lisp
>> 
>> A chum of me just implemented a permutation function that works in
>> constant space by only swapping in a fixed array without any copying.
>> I've taken a look at it and it's seems to be rather impressive. It's not
>> written in CL but in Pascal but it should be easy portable.
>> I'll ask him next time I see him.
> 
> this isn't all that hard if you look at it right.
> 
> consider this --
> 
> you have an array of N items A and an empty array B of N places.
> 
> take one item (at random) from A, say for the sake of argment, it's
> element 14.  put it in B.
> 
> you don't want to take this item again.  you could mark this item as
> taken by writing a special token there.  however, you could just copy
> the 1st element into element 14 and let the new A be elements 2
> through N.
> 
> take another item from 2 to N from A.  let it be 27.  copy A[27] to
> B[2].  copy A[2] to A[27].
> 
> take an item from 3 to N...
> 
> notice that B never holds more than one more element than you've taken
> from A.
> 
> implement this by using the dead part of A (the initial bit which
> you've moved upwards the elements you've claimed) to store B.
> 
> thus you iterate upwards through the array and swap the I-th element
> with a random one takes from I through N inclusive (sometimes you
> "swap" with itself).
> 
> hope this helps.

sounds usable (But I've not read it very detailed).
But my chums algorithm doesn't use any tags or similar.
He uses a timely displaced left->right right->left bouncing
of the elements. I'll ask him next days...

Regards,
Jochen
From: Johan Kullstam
Subject: Re: Permutations
Date: 
Message-ID: <m3k88cg421.fsf@sysengr.res.ray.com>
Jochen Schmidt <···@dataheaven.de> writes:

> Johan Kullstam wrote:
> 
> > Jochen Schmidt <···@dataheaven.de> writes:
> > 
> >> glauber wrote:
> >> 
> >> > In article <·····················@news3.cableinet.net>,
> >> >   "Grant Henderson" <·········@cableinet.co.uk> wrote:
> >> >> Has anybody got any algorithms or code that works out all the
> >> >> permutations for a given set {1n,2n,.......Nn}
> >> > 
> >> > 
> >> > I asked this here a while ago and got a lot of interesting responses,
> >> > including code.
> >> > 
> >> > See if this URL works for you:
> >> > http://www.deja.com/viewthread.xp?AN=674042477&group=comp.lang.lisp
> >> 
> >> A chum of me just implemented a permutation function that works in
> >> constant space by only swapping in a fixed array without any copying.
> >> I've taken a look at it and it's seems to be rather impressive. It's not
> >> written in CL but in Pascal but it should be easy portable.
> >> I'll ask him next time I see him.
> > 
> > this isn't all that hard if you look at it right.
> > 
> > consider this --
> > 
> > you have an array of N items A and an empty array B of N places.
> > 
> > take one item (at random) from A, say for the sake of argment, it's
> > element 14.  put it in B.
> > 
> > you don't want to take this item again.  you could mark this item as
> > taken by writing a special token there.  however, you could just copy
> > the 1st element into element 14 and let the new A be elements 2
> > through N.
> > 
> > take another item from 2 to N from A.  let it be 27.  copy A[27] to
> > B[2].  copy A[2] to A[27].
> > 
> > take an item from 3 to N...
> > 
> > notice that B never holds more than one more element than you've taken
> > from A.
> > 
> > implement this by using the dead part of A (the initial bit which
> > you've moved upwards the elements you've claimed) to store B.
> > 
> > thus you iterate upwards through the array and swap the I-th element
> > with a random one takes from I through N inclusive (sometimes you
> > "swap" with itself).
> > 
> > hope this helps.
> 
> sounds usable (But I've not read it very detailed).
> But my chums algorithm doesn't use any tags or similar.
> He uses a timely displaced left->right right->left bouncing
> of the elements. I'll ask him next days...

ok i whipped this up

;; destructively permute a vector
(defun n-randomly-permute-vector (vec)
  (let ((len (length vec)))
    (loop :for i :of-type fixnum :from (1- len) :downto 1
	  :do (let ((j (random i)))
		(unless (eql i j)
		  (rotatef (aref vec i)
			   (aref vec j))))))
  vec)

;; make an index vector #(0 1 2 ... n)
(defun iota (n)
  (let ((vec (make-array n)))
    (dotimes (i n)
      (setf (aref vec i) i))
    vec))

and took it for a test drive

* (n-randomly-permute-vector (iota 4))
#(1 3 0 2)
* (n-randomly-permute-vector (iota 4))
#(1 3 0 2)
* (n-randomly-permute-vector (iota 4))
#(3 0 1 2)
* (n-randomly-permute-vector (iota 18))
#(1 3 0 2)
* (n-randomly-permute-vector (iota 18))
#(9 12 10 1 15 3 2 4 0 16 5 6 7 17 11 13 14 8)
* (n-randomly-permute-vector (iota 18))
#(16 8 3 5 7 12 17 13 11 0 9 15 6 2 1 4 14 10)

i counted downwards instead of upwards.  you can make a
non-destructive version by changing (aref vec i) to (aref new-vec i)
and creating and returning new-vec where appropriate.

hope this helps.

-- 
J o h a n  K u l l s t a m
[········@ne.mediaone.net]
sysengr
From: Jochen Schmidt
Subject: Re: Permutations
Date: 
Message-ID: <92vaut$8e6ik$1@ID-22205.news.dfncis.de>
Johan Kullstam wrote: 
> ok i whipped this up
> 
> ;; destructively permute a vector
> (defun n-randomly-permute-vector (vec)
>   (let ((len (length vec)))
>     (loop :for i :of-type fixnum :from (1- len) :downto 1
> :do (let ((j (random i)))
> (unless (eql i j)
> (rotatef (aref vec i)
> (aref vec j))))))
>   vec)
> 
> ;; make an index vector #(0 1 2 ... n)
> (defun iota (n)
>   (let ((vec (make-array n)))
>     (dotimes (i n)
>       (setf (aref vec i) i))
>     vec))
> 
> and took it for a test drive
> 
> * (n-randomly-permute-vector (iota 4))
> #(1 3 0 2)
> * (n-randomly-permute-vector (iota 4))
> #(1 3 0 2)
> * (n-randomly-permute-vector (iota 4))
> #(3 0 1 2)
> * (n-randomly-permute-vector (iota 18))
> #(1 3 0 2)
> * (n-randomly-permute-vector (iota 18))
> #(9 12 10 1 15 3 2 4 0 16 5 6 7 17 11 13 14 8)
> * (n-randomly-permute-vector (iota 18))
> #(16 8 3 5 7 12 17 13 11 0 9 15 6 2 1 4 14 10)
> 
> i counted downwards instead of upwards.  you can make a
> non-destructive version by changing (aref vec i) to (aref new-vec i)
> and creating and returning new-vec where appropriate.

Yes thats Fisher-Yates as I remember but if you don't only want the 
nth-permutation or as in your case *a* random permutation - i. e if
you want _all_ permutations (each exaclty one times) then you have to copy
the initial vector by using Fisher-Yates.
The algorithm of my chum doesn't need any copying (only in-place swapping
of elements) and is therefore constant in space. (as I remember)

Regards,
Jochen
From: ··········@my-deja.com
Subject: Re: Permutations
Date: 
Message-ID: <930047$kob$1@nnrp1.deja.com>
In article <··············@ID-22205.news.dfncis.de>,
  Jochen Schmidt <···@dataheaven.de> wrote:
> The algorithm of my chum doesn't need any copying (only in-place
swapping
> of elements) and is therefore constant in space. (as I remember)

"Needs no copying" does not imply "is constant in space".
Here's what I usually do:  Maybe it's similar to what your friend used.


(defun permute (arr func &optional (start 0) (end (length arr)))
  "Permute ARR's elements between START and END.  For each
permutation, call FUNC, passing either ARR itself (in-place
permutation) or a shallow copied permutation of ARR as the only
parameter.  FUNC is neither allowed to modify ARR nor the parameter it
got.

permute's return value is unspecified.  After permute returns, ARR's
elements will be in their original order."
  (declare (type (array * (*)) arr)
	   (function func)
	   (fixnum start end))
  (if (>= start (1- end))
    (funcall func arr)
    (loop for i fixnum from start below end
          do (progn
               (rotatef (aref arr i) (aref arr start))
               (permute arr func (1+ start) end)
               (rotatef (aref arr i) (aref arr start))))))


* (permute (make-array 3 :initial-contents '(0 1 2)) #'print)
#(0 1 2)
#(0 2 1)
#(1 0 2)
#(1 2 0)
#(2 1 0)
#(2 0 1)
NIL


If N is (- end start), permute implicitly uses O(N) stack space for the
recursion; but as the input itself uses O(N) space and must be
completely available when calling permute, this seems like an acceptable
overhead.  The time complexity is O(N!), which is the lower bound, as N!
calls to func are needed.  permute does not cons.


HTH.


Sent via Deja.com
http://www.deja.com/
From: Yuan
Subject: Re: Permutations
Date: 
Message-ID: <60d7dxuxqa.fsf@wonka.cs.umd.edu>
··········@my-deja.com writes:
...
> If N is (- end start), permute implicitly uses O(N) stack space for the
> recursion; but as the input itself uses O(N) space and must be
> completely available when calling permute, this seems like an acceptable
> overhead.  The time complexity is O(N!), which is the lower bound, as N!
> calls to func are needed.  permute does not cons.

Here is a non-recursive implementation, which is quite faster.  It
generates (and compiles) code dynamically during runtime (when necessary)
to speed up the execution.  No garbage is generated, and no extra space
allocated, after the compilation; some lisp constructs may have been
abused, though. :)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defmacro %do-permutations ((var vec) &body body)
  "Bind VAR to each permutation of elements of VEC, and evaluate BODY.
VEC must be a vector constant."
  (let* ((body `(progn ,@body))
	 (mag (length (eval vec))))
    (dotimes (i (1- mag))
      (let ((sym (gensym)))
	(setf body `(dotimes (,sym ,(+ i 2))
		      (declare (type (mod ,(1+ mag)) ,sym))
		      ,body
		      (rotatef
		        (aref ,var ,(if (evenp i) 0 sym))
		        (aref ,var ,(+ i 1)))))))
    `(let ((,var (copy-seq ,vec)))
      (declare (optimize speed) (type (simple-array * (,mag)) ,var))
      ,body)))

(defun gen-permutation-code (vec)
  "Generate a function (f1) of one argument (f2), which should be a
function (f2) of one argument (a1).  The generated function (f1) will
funcall its argument function (f2) with each permutation (as vector VEC) as
its argument (a1)."
  (let ((fun (gensym)) (var (gensym)))
    `(lambda (,fun)
      (declare (function ,fun))
      ,(macroexpand `(%do-permutations (,var ,vec)
		      (funcall ,fun ,var))))))

(defun map-permutations (fun vec)
  "Funcall FUN with each permutation as vector VEC."
  (funcall (compile nil (gen-permutation-code vec)) fun))

(defmacro do-permutations ((var vec) &body body)
  "Bind VAR to each permutation as vector VEC, and evaluate BODY."
  (if (constantp vec)
      `(%do-permutations (,var ,vec) ,@body)
      `(map-permutations (lambda (,var) ,@body) ,vec)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; transcript
On Sun Ultra 5/10 UPA/PCI (UltraSPARC-IIi 333MHz)

* CMU Common Lisp 18c, Built 2000-11-28, running on localhost.
...
* (do-permutations (x "abcd") (format t "~A " x))
abcd bacd cbad bcad cabd acbd dabc adbc badc abdc bdac dbac cdab dcab adcb dacb acdb cadb bcda cbda dcba cdba dbca bdca 
NIL
* (gen-permutation-code "abc")
(LAMBDA (#:G869)
  (DECLARE #'#:G869)
  (LET ((#:G870 (COPY-SEQ "abc")))
    (DECLARE (OPTIMIZE SPEED) (TYPE (SIMPLE-ARRAY * (3)) #:G870))
    (DOTIMES (#:G872 3)
      (DECLARE (TYPE (MOD 4) #:G872))
      (DOTIMES (#:G871 2)
        (DECLARE (TYPE (MOD 4) #:G871))
        (PROGN (FUNCALL #:G869 #:G870))
        (ROTATEF (AREF #:G870 0) (AREF #:G870 1)))
      (ROTATEF (AREF #:G870 #:G872) (AREF #:G870 2)))))
* (time (map-permutations (lambda (x) (declare (ignore x))) "abcdefghijk"))
Compiling LAMBDA NIL: 
Compiling Top-Level Form: 
Compiling LAMBDA (#:G873): 
Compiling Top-Level Form: 

Evaluation took:
  12.51 seconds of real time
  12.47 seconds of user run time
  0.01 seconds of system run time
  0 page faults and
  1277392 bytes consed.
NIL
* (time (do-permutations (x "abcdefghijk")))
Compiling LAMBDA NIL: 
Compiling Top-Level Form: 

Evaluation took:
  6.28 seconds of real time
  6.26 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  72 bytes consed.
NIL
* (time (permute "abcdefghijk" (lambda (x) (declare (ignore x)))))
Compiling LAMBDA NIL: 
Compiling Top-Level Form: 

Evaluation took:
  246.77 seconds of real time
  246.47 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  48 bytes consed.
NIL
From: Geoffrey Summerhayes
Subject: Re: Permutations
Date: 
Message-ID: <1qU46.22706$n%.1154063@news20.bellglobal.com>
"Grant Henderson" <·········@cableinet.co.uk> wrote in message
··························@news3.cableinet.net...
> Has anybody got any algorithms or code that works out all the
> permutations for a given set {1n,2n,.......Nn}
>
> Anything would be great
> Cheers
> Grant

Knuth,Knuth,Knuth,Knuth,
Knuth,Knuth,Knuth,Knuth,KNUTH!

Or, P.G.P's impl. in c++ stl. Shoot me, it's nice code!