From: The Glauber
Subject: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8qojjq$lr5$1@nnrp1.deja.com>
(this is not homework; i'm not even in school anymore :-))
I'm a novice in Lisp, so bear with me if this is a stupid question.
I've been playing with generating all permutations of a list.
I wrote the following, based on a similar function by Daniel Nesmith:
(defun permute-list (l)
"Returns a list of all permutations of the input list (list of lists)."
(if (< (length l) 2)
(list l)
; insert the first element in each position of
; the permutation of the other elements of the
; original list
(mapcan
#'(lambda (seq)
(let ((res-list nil))
(dotimes (i (length l) res-list)
(push
(nconc (subseq seq 0 i)
(cons (first l) (subseq seq i)))
res-list))))
(permute-list (rest l)))))
This works. I think it must consume a lot of memory for lists
of more than a few elements.
Are there any obvious optimizations i missed?
Is there any way to make this tail-recursive?
I thought about this most of the day today, but i can't see it.
The next step, i guess, would be to write a macro with-all-permutations,
which would take a list and a block, and run that block once for
each of the permutations of the list. But i can't see how to do that
without first going through the whole process of generating all the
permutations...
Thanks for any insights.
'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/
Before you buy.
From: Jason Kantz
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <wkpulrp4x1.fsf@kantz.com>
The Glauber <··········@my-deja.com> writes:
> (defun permute-list (l)
> "Returns a list of all permutations of the input list (list of lists)."
> (if (< (length l) 2)
> (list l)
> ; insert the first element in each position of
> ; the permutation of the other elements of the
> ; original list
> (mapcan
> #'(lambda (seq)
> (let ((res-list nil))
> (dotimes (i (length l) res-list)
> (push
> (nconc (subseq seq 0 i)
> (cons (first l) (subseq seq i)))
> res-list))))
> (permute-list (rest l)))))
[snip]
> Are there any obvious optimizations i missed?
You can save a few steps by changing your base case from
(< (length l) 2) to (endp (cdr l))
--
Jason Kantz
http://kantz.com/jk
From: Michael Kappert
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <39D09CA3.54E94EA8@iitb.fhg.de>
The Glauber wrote:
> I wrote the following, based on a similar function by Daniel Nesmith:
>
> (defun permute-list (l)
> "Returns a list of all permutations of the input list (list of lists)."
> (if (< (length l) 2)
> (list l)
> ; insert the first element in each position of
> ; the permutation of the other elements of the
> ; original list
> (mapcan
> #'(lambda (seq)
> (let ((res-list nil))
> (dotimes (i (length l) res-list)
> (push
> (nconc (subseq seq 0 i)
> (cons (first l) (subseq seq i)))
> res-list))))
> (permute-list (rest l)))))
> Are there any obvious optimizations i missed?
Not in terms of complexity, but a technical optimization:
MAPCAN + LAMBDA is slow. Use LOOP ... NCONC + body instead.
And because i like short code I'd replace the DOTIMES as well,
getting rid of the LET :-)
(defun permute-list (l)
"Returns a list of all permutations of the input list (list of lists)."
(if (< (length l) 2)
(list l)
;; insert the first element in each position of
;; the permutation of the other elements of the
;; original list
(loop for seq in (permute-list (rest l))
nconc (loop for i below (length l)
collect (nconc (subseq seq 0 i)
(cons (first l) (subseq seq i)))))
> The next step, i guess, would be to write a macro with-all-permutations,
> which would take a list and a block, and run that block once for
> each of the permutations of the list. But i can't see how to do that
> without first going through the whole process of generating all the
> permutations...
Write a function that returns the n-th permutation wrt. some order of the
permutations. The following function orders permutations by the number of
swaps of adjacent elements needed to produce a permutation from the
original sequence.
(defun nth-permutation (n sequence)
(do ((l (1- (length sequence)) (1- l))
(k 0 (1+ k)))
((= l 0) sequence)
(multiple-value-bind (q r) (truncate n (faculty l))
(setf n r)
(rotatef (elt sequence k) (elt sequence (+ k q))))))
where faculty is your favourite implementation of n!.
Michael
--
From: Michael Kappert
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <39D0A187.4AC012EB@iitb.fhg.de>
I wrote:
> Write a function that returns the n-th permutation wrt. some order of the
^^^^
some total order is needed, of course...
> permutations. The following function orders permutations by the number of
> swaps of adjacent elements needed to produce a permutation from the
> original sequence.
...only that doesn't define a total order.
Permutations with equal numbers of adjacent swaps are in lexicographic order,
i think.
> (defun nth-permutation (n sequence)
> (do ((l (1- (length sequence)) (1- l))
> (k 0 (1+ k)))
> ((= l 0) sequence)
> (multiple-value-bind (q r) (truncate n (faculty l))
> (setf n r)
> (rotatef (elt sequence k) (elt sequence (+ k q))))))
>
> where faculty is your favourite implementation of n!.
Michael
--
From: Will Mengarini
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8r4p2b$51g$1@eskinews.eskimo.com>
This makes multiple versions of recursive functions more convenient:
(defmacro adefun (name arglist &body body)
"Anaphoric defun, where `self' is a synonym for function name.
Works for not just recursion but e.g. \"return-from self\" and \"#'self\".
Inspired by Graham /On Lisp/, q.v."
;; That couldn't be done with #'symbol-macrolet or #'labels.
(labels ((f (tree) (if (atom tree)
(if (eq tree 'self)
name
tree)
(cons (f (car tree))
(f (cdr tree))))))
`(defun ,name ,arglist ,@(f body))))
With that, when you rename the functions so they'll have
distinct names, you don't need to also dig into the
function code and change the recursive self-invocations.
--
Will Mengarini <······@eskimo.com>
Free software: the Source will be with you, always.
From: The Glauber
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8qqc7j$ll9$1@nnrp1.deja.com>
In article <·················@iitb.fhg.de>,
Michael Kappert <···@iitb.fhg.de> wrote:
Thanks for your reply. Your version is a little faster, as expected (i'm
testing with CLISP under Windows 98).
What's collect? It doesn't seem to be in the Hyperspec.
glauber
[...]
> Not in terms of complexity, but a technical optimization:
> MAPCAN + LAMBDA is slow. Use LOOP ... NCONC + body instead.
> And because i like short code I'd replace the DOTIMES as well,
> getting rid of the LET :-)
>
> (defun permute-list (l)
> "Returns a list of all permutations of the input list (list of lists)."
> (if (< (length l) 2)
> (list l)
> ;; insert the first element in each position of
> ;; the permutation of the other elements of the
> ;; original list
> (loop for seq in (permute-list (rest l))
> nconc (loop for i below (length l)
> collect (nconc (subseq seq 0 i)
> (cons (first l) (subseq seq i)))))
>
--
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/
Before you buy.
From: Michael Kappert
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <39D0BF5B.E3592C7A@iitb.fhg.de>
The Glauber wrote:
> What's collect? It doesn't seem to be in the Hyperspec.
It's a LOOP keyword, as is the first occurrence of NCONC in
the function below. See Section 6.1.3 in the HyperSpec.
Michael
>
> glauber
>
> [...]
> > Not in terms of complexity, but a technical optimization:
> > MAPCAN + LAMBDA is slow. Use LOOP ... NCONC + body instead.
> > And because i like short code I'd replace the DOTIMES as well,
> > getting rid of the LET :-)
> >
> > (defun permute-list (l)
> > "Returns a list of all permutations of the input list (list of lists)."
> > (if (< (length l) 2)
> > (list l)
> > ;; insert the first element in each position of
> > ;; the permutation of the other elements of the
> > ;; original list
> > (loop for seq in (permute-list (rest l))
> > nconc (loop for i below (length l)
> > collect (nconc (subseq seq 0 i)
> > (cons (first l) (subseq seq i)))))
> >
>
> --
> 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/
> Before you buy.
--
From: Thomas A. Russ
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <ymiaecvt61s.fsf@sevak.isi.edu>
The Glauber <··········@my-deja.com> writes:
I have two additional optimizations in the code below. One is to move
the call to (length l) out of the inner loop and the other is to
eliminate the second subseq call by using CDR to move down the list.
> > (defun permute-list (l)
> > "Returns a list of all permutations of the input list (list of lists)."
> > (if (< (length l) 2)
> > (list l)
> > ;; insert the first element in each position of
> > ;; the permutation of the other elements of the
> > ;; original list
REPLACE THIS:
> > (loop for seq in (permute-list (rest l))
> > nconc (loop for i below (length l)
> > collect (nconc (subseq seq 0 i)
> > (cons (first l) (subseq seq i)))))
WITH:
(loop with len = (length l)
with first-element = (first l)
for seq in (permute-list (rest l))
nconc (loop for i below (length l)
as tail = seq then (cdr tail)
collect (nconc (subseq seq 0 i)
(cons first-element tail))))
))
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
From: Thomas A. Russ
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <ymi4s32u4ml.fsf@sevak.isi.edu>
···@sevak.isi.edu (Thomas A. Russ) writes:
> The Glauber <··········@my-deja.com> writes:
>
> I have two additional optimizations in the code below. One is to move
> the call to (length l) out of the inner loop and the other is to
> eliminate the second subseq call by using CDR to move down the list.
>
> > > (defun permute-list (l)
> > > "Returns a list of all permutations of the input list (list of lists)."
> > > (if (< (length l) 2)
> > > (list l)
> > > ;; insert the first element in each position of
> > > ;; the permutation of the other elements of the
> > > ;; original list
>
> REPLACE THIS:
>
> > > (loop for seq in (permute-list (rest l))
> > > nconc (loop for i below (length l)
> > > collect (nconc (subseq seq 0 i)
> > > (cons (first l) (subseq seq i)))))
>
> WITH:
>
> (loop with len = (length l)
> with first-element = (first l)
> for seq in (permute-list (rest l))
> nconc (loop for i below (length l)
> as tail = seq then (cdr tail)
> collect (nconc (subseq seq 0 i)
> (cons first-element tail))))
> ))
OK, following up to my own post. You can improve this even more by
eliminating the internal collect and nconc the results by just pushing
the results onto a collection variable. In the case of permutations, it
doesn't really matter what order they are generated in:
(loop with len = (length l)
with first-element = (first l)
with result = nil
for seq in (permute-list (rest l))
do (loop for i below (length l)
as tail = seq then (cdr tail)
do (push (nconc (subseq seq 0 i)
(cons first-element tail))
result))
finally (return result))
))
From: The Glauber
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8qsu5p$s5a$1@nnrp1.deja.com>
Thanks to all who replied. I have a lot of catching up to do before i
understand these changes, but i'm working on it. Again, thanks!
Since nobody proposed one, i'm assuming that there isn't any tail-recursive
solution to this problem?
Isn't there a method one can use to transform any recursive problem into
tail-recursive? I thought there was one, but i was probably being too
optimistic then.
Thanks,
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/
Before you buy.
From: Lieven Marchand
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <m3pulpvkpd.fsf@localhost.localdomain>
The Glauber <··········@my-deja.com> writes:
> Isn't there a method one can use to transform any recursive problem into
> tail-recursive? I thought there was one, but i was probably being too
> optimistic then.
Look for CPS (continuation passing style) programming. It's not very
practicle to do by hand but some compilers use it, including Steele's
original RABBIT compiler for Scheme.
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club
From: Xenophon Fenderson the Carbon(d)ated
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <w4o3dil2trm.fsf@lovecraft.irtnog.org>
>>>>> "Lieven" == Lieven Marchand <···@bewoner.dma.be> writes:
Lieven> Look for CPS (continuation passing style)
Lieven> programming. It's not very practicle to do by hand but
Lieven> some compilers use it, including Steele's original RABBIT
Lieven> compiler for Scheme.
How in the world does one automate it (i.e. recognize recursion and
transform it to CPS)? I would have said it's much easier to do by
hand, then write a transformation function to do it.
--
UN-altered reproduction and DISSEMINATION of this IMPORTANT information is
ENCOURAGED
From: Lieven Marchand
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <m3g0mk4gd0.fsf@localhost.localdomain>
········@irtnog.org (Xenophon Fenderson the Carbon(d)ated) writes:
> >>>>> "Lieven" == Lieven Marchand <···@bewoner.dma.be> writes:
>
> Lieven> Look for CPS (continuation passing style)
> Lieven> programming. It's not very practicle to do by hand but
> Lieven> some compilers use it, including Steele's original RABBIT
> Lieven> compiler for Scheme.
>
> How in the world does one automate it (i.e. recognize recursion and
> transform it to CPS)? I would have said it's much easier to do by
> hand, then write a transformation function to do it.
It doesn't try to recognize recursion, it transforms everything to
explicitly hand in an argument representing the rest of the
computation to hand the result to (the current continuation). It's a
reasonable strategy to compile scheme since scheme reifies the cc. You
can find more detailed info in "Lisp in Small Pieces" and in Apple's
"Compiling with continuations".
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club
Lieven Marchand wrote:
> It doesn't try to recognize recursion, it transforms everything to
> explicitly hand in an argument representing the rest of the
> computation to hand the result to (the current continuation). It's a
> reasonable strategy to compile scheme since scheme reifies the cc. You
> can find more detailed info in "Lisp in Small Pieces" and in Apple's
> "Compiling with continuations".
I think you mean "Appel", not "Apple". Biiig difference. :-)
--
Gareth McCaughan ················@pobox.com
sig under construc
From: Lieven Marchand
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <m31yy3ywmg.fsf@localhost.localdomain>
················@pobox.com (Gareth McCaughan) writes:
> Lieven Marchand wrote:
>
> > It doesn't try to recognize recursion, it transforms everything to
> > explicitly hand in an argument representing the rest of the
> > computation to hand the result to (the current continuation). It's a
> > reasonable strategy to compile scheme since scheme reifies the cc. You
> > can find more detailed info in "Lisp in Small Pieces" and in Apple's
> > "Compiling with continuations".
>
> I think you mean "Appel", not "Apple". Biiig difference. :-)
Thanks for the correction. I even have one of his books laying around
in plain sight and I still can't get it right. Probably because appel
is the dutch word for apple and I was writing english ;-)
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club
From: Harley Davis
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <39da3ec3$0$228@newsreader.alink.net>
"The Glauber" <··········@my-deja.com> wrote in message
·················@nnrp1.deja.com...
> Thanks to all who replied. I have a lot of catching up to do before i
> understand these changes, but i'm working on it. Again, thanks!
>
> Since nobody proposed one, i'm assuming that there isn't any
tail-recursive
> solution to this problem?
>
> Isn't there a method one can use to transform any recursive problem into
> tail-recursive? I thought there was one, but i was probably being too
> optimistic then.
The only way to transfer all recursive functions into tail-recursive
functions is to use an explicit stack object to replace the call stack. But
you don't gain anything by doing that either in terms of memory use or time,
and just add additional work for yourself. The CPS method mentioned in
other articles is really nothing more than embedding the stack in a
continuation object, so this doesn't provide the benefits of tail recursion
either.
More fundamentally, you can't change a computation that requires unbounded
resources into a computation using bounded resources.
-- Harley
From: Barry Margolin
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <bhrC5.34$kQ5.384@burlma1-snr2>
In article <··············@newsreader.alink.net>,
Harley Davis <·············@nospam.museprime.com> wrote:
>The only way to transfer all recursive functions into tail-recursive
>functions is to use an explicit stack object to replace the call stack.
It depends on what you're doing. If you're accumulating a list of things,
you're right. But if you're accumulating an arithmetic result, you can
often replace the stacked computations with an explicit accumulator that's
passed. The classic example is the tail recursive version of factorial,
which is essentially equivalent to an iterative version.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: The Glauber
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8rdhmu$etd$1@nnrp1.deja.com>
In article <················@burlma1-snr2>,
Barry Margolin <······@genuity.net> wrote:
> In article <··············@newsreader.alink.net>,
> Harley Davis <·············@nospam.museprime.com> wrote:
> >The only way to transfer all recursive functions into tail-recursive
> >functions is to use an explicit stack object to replace the call
stack.
>
> It depends on what you're doing. If you're accumulating a list of
things,
> you're right. But if you're accumulating an arithmetic result, you
can
> often replace the stacked computations with an explicit accumulator
that's
> passed. The classic example is the tail recursive version of
factorial,
> which is essentially equivalent to an iterative version.
>
I guess the problem here is the ambiguity of the English language in
this context. You can convert some recursive computations to iterative
(e.g. factorial), but you can't convert all recursive computations to
iterative (tail-recursive being pretty much an iterative computation
masquerading as recursive).
If the recursive computation requires unbound resources than it can't be
converted to iterative. I'm no mathematician, but i think we can say
that if the function needs to access the intermediate results in order
to achieve its final result, then it requires unbound resources, and
can't be converted. In this case, the permutation function needs to
access each of the intermediate results as it builds the list of
permutations.
I was hoping there would be another algorythm to do the same thing
without using unbound resources, but nobody has volunteered one yet. :-)
Thanks to all who replied; i feel i learned a lot through this
discussion.
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/
Before you buy.
From: Erik Naggum
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <3179671668484915@naggum.net>
* The Glauber <··········@my-deja.com>
| I'm a novice in Lisp, so bear with me if this is a stupid question.
| I've been playing with generating all permutations of a list.
| I wrote the following, based on a similar function by Daniel Nesmith:
|
| (defun permute-list (l)
| "Returns a list of all permutations of the input list (list of lists)."
| (if (< (length l) 2)
| (list l)
| ; insert the first element in each position of
| ; the permutation of the other elements of the
| ; original list
| (mapcan
| #'(lambda (seq)
| (let ((res-list nil))
| (dotimes (i (length l) res-list)
| (push
| (nconc (subseq seq 0 i)
| (cons (first l) (subseq seq i)))
| res-list))))
| (permute-list (rest l)))))
I tend to favor a slight different approach:
(defun permutations (list)
(if (cdr list)
(loop with rotation = list
do (setq rotation (nconc (last rotation) (nbutlast rotation)))
nconc (loop for list in (permutations (rest rotation))
collect (cons (first rotation) (copy-list list)))
until (eq rotation list))
(list list)))
It is about 20 times faster with an 8-element list to permute, but
as it turns out, it is significantly more memory-intensive than your
approach (4.4 times). (Measured with Allegro CL 6.0.)
| Are there any obvious optimizations i missed?
That (setq rotation (nconc (last rotation) (nbutlast rotation)))
eventually returns the original list and that it can thus be used in
a recursive function to avoid duplicating the control structre is
not obvious (according to a colleague I showed this to :). That
particular expression may also be optimized to traverse the list
only once, if you really have to. (For a 10-element list, 98% of
the time is spent in garbage collection.)
| Is there any way to make this tail-recursive?
More interesting than this unnatural obsession with tail-recursion
is how deep your recursion is relative to the length of the input.
If you can't immediately tell, you need to spend more time with
recursion and completely forget tail-recursion until you can get a
sufficiently good "gut feeling" for maximal recursion depths.
| The next step, i guess, would be to write a macro
| with-all-permutations, which would take a list and a block, and run
| that block once for each of the permutations of the list. But i
| can't see how to do that without first going through the whole
| process of generating all the permutations...
Pass in a function call, wrap the macro body in a lambda, and off
you go. Remember to do this only at the top-level call, and default
to some innocuous function like identity.
#:Erik
--
If this is not what you expected, please alter your expectations.
From: The Glauber
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8rg2i4$h9d$1@nnrp1.deja.com>
Thanks for your reply!
In article <················@naggum.net>,
Erik Naggum <····@naggum.net> wrote:
[...]
> | Is there any way to make this tail-recursive?
>
> More interesting than this unnatural obsession with tail-recursion
> is how deep your recursion is relative to the length of the input.
> If you can't immediately tell, you need to spend more time with
> recursion and completely forget tail-recursion until you can get a
> sufficiently good "gut feeling" for maximal recursion depths.
[...]
It's probably because i learned Scheme (via DSSSL) before learning CL.
:-)
Your definition does use more memory. In CLISP under Windoze (running
inside emacs) i can't permute more than 7 elements with it. For lists
that small, the other approach is faster (maybe because of the time
spent allocating memory and GC-ing). Times: the other approach took .9s
interpreted, .65s compiled, yours took 4.4s, 1.21s compiled.
Thanks again!
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/
Before you buy.
From: Bernhard Pfahringer
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8rgqhf$8ql@borg.cs.waikato.ac.nz>
In article <················@naggum.net>, Erik Naggum <····@naggum.net> wrote:
>
>(defun permutations (list)
> (if (cdr list)
> (loop with rotation = list
> do (setq rotation (nconc (last rotation) (nbutlast rotation)))
> nconc (loop for list in (permutations (rest rotation))
> collect (cons (first rotation) (copy-list list)))
> until (eq rotation list))
> (list list)))
>
Most likely this will work in all implementations, but it is not
guaranteed to do so. You would need to test (equal rotation list),
as nbutlast *may* modify its argument, but it does not have to.
Also memory-consumption could be reduced by replacing
(copy-list list) simply with list, thereby allowing permutations
to share common suffixes.
And of course I had to do a slightly modified version as well :-)
(defun permutations (list)
(if (cdr list)
(loop for point on list
nconc
(prog2 (rotatef (first list) (first point))
(loop for l1 in (permutations (rest list))
collect
(cons (first list) l1))
(rotatef (first list) (first point))))
(list (copy-list list))))
cheers, Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
G1.25, 838 4041, ········@cs.waikato.ac.nz
--------------------------------------------------------------------------
From: Erik Naggum
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <3179726196411119@naggum.net>
* Bernhard Pfahringer
| Most likely this will work in all implementations, but it is not
| guaranteed to do so. You would need to test (equal rotation list),
| as nbutlast *may* modify its argument, but it does not have to.
The argument shouldn't be modified when it's too short, which is the
case I find covered by that "may", not some broken implementation
that fails to get the whole point of the nbutlast operator. So if
it doesn't, complain vociferously to your vendor, and follow my
advice to optimize this by doing your own cons cell hacking.
| Also memory-consumption could be reduced by replacing
| (copy-list list) simply with list, thereby allowing permutations
| to share common suffixes.
They would share common suffixes, allright, but those suffixes would
then continue to change as the whole point of this implementation is
to rotate the elements of the list in place by cons cell hacking.
(Please try out your suggestions before posting them. It is quite
inconsiderate towards your readers to want all of them to try what
you suggest only to find that it doesn't work when you could have
avoided giving false advice by trying it out yourself. There's also
an insult to the intelligence of the writer of the first code to
assume that doing a copy-list had no purpose or even good reason.
However, I'm not thrilled with the memory consumption myself, so any
working optimization is definitely welcome.)
| And of course I had to do a slightly modified version as well :-)
Meta-permutation? :)
#:Erik
--
If this is not what you expected, please alter your expectations.
From: Bernhard Pfahringer
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <8rir6u$b30@borg.cs.waikato.ac.nz>
In article <················@naggum.net>, Erik Naggum <····@naggum.net> wrote:
>
> (Please try out your suggestions before posting them. It is quite
> inconsiderate towards your readers to want all of them to try what
> you suggest only to find that it doesn't work when you could have
> avoided giving false advice by trying it out yourself. There's also
> an insult to the intelligence of the writer of the first code to
> assume that doing a copy-list had no purpose or even good reason.
> However, I'm not thrilled with the memory consumption myself, so any
> working optimization is definitely welcome.)
>
You're right that the suggested modification to your code is incorrect.
Sorry for that, this was not a deliberate insult, simply dumbness.
I thought I'd tested it, but obviously I was wrong. Anyway, no need
to go overboard, just a typical case of "don't assume malice, where
incompetence or ignorace suffices :-)"
Nevertheless, my "meta-permutation" is bug-free and efficient.
And while we are it, here is another variant that just enumerates
all permutations and allows you to call a function for each
permutation instead of collecting all permutations:
(defun permute (list continuation)
(if (cdr list)
(loop for point on list
do
(rotatef (first list) (first point))
(permute (rest list) continuation)
(rotatef (first list) (first point)))
(funcall continuation)))
pretty simple and obvious code and much more versatile.
So if you wanted to count the number of permutations
(effectively a rather expensive way of computing N!)
(defun number-of-permutations (list)
(let ((n 0))
(permute list
(lambda () (incf n)))
n))
To collect all permutations (unfortunately without sharing of
common suffixes):
(defun collect-permutations (list)
(let ((permutations nil))
(permute list
(lambda () (push (copy-list list) permutations)))
permutations))
Our simply print them for inspection:
(defun print-permutations (list)
(permute list
(lambda () (print list))))
cheers, Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
G1.25, 838 4041, ········@cs.waikato.ac.nz
--------------------------------------------------------------------------
In article <··········@borg.cs.waikato.ac.nz>,
········@borg.cs.waikato.ac.nz (Bernhard Pfahringer) wrote:
> Nevertheless, my "meta-permutation" is bug-free and efficient.
> And while we are it, here is another variant that just enumerates
> all permutations and allows you to call a function for each
> permutation instead of collecting all permutations:
>
> (defun permute (list continuation)
> (if (cdr list)
> (loop for point on list
> do
> (rotatef (first list) (first point))
> (permute (rest list) continuation)
> (rotatef (first list) (first point)))
> (funcall continuation)))
Just about the variable name. Above
variable is not really a continuation.
A continuation is possibly changing
the control flow. Here the single function is
just applied to a data element, does something
and returns.
--
Rainer Joswig, Hamburg, Germany
Email: ·············@corporate-world.lisp.de
Web: http://corporate-world.lisp.de/
From: Erik Naggum
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <3179816214881486@naggum.net>
* Bernhard Pfahringer
| You're right that the suggested modification to your code is incorrect.
| Sorry for that, this was not a deliberate insult, simply dumbness.
| I thought I'd tested it, but obviously I was wrong. Anyway, no need
| to go overboard, just a typical case of "don't assume malice, where
| incompetence or ignorace suffices :-)"
Well, I'd rather have malice any day over incompetence and ignorance
used as excuses -- you can at least do something about the malice.
["Thank God children never mean well." -- Lily Tomlin]
Your original code looks good, though.
#:Erik
--
If this is not what you expected, please alter your expectations.
From: Guy Footring
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <wk1yxv1v6p.fsf@ford.com>
········@borg.cs.waikato.ac.nz (Bernhard Pfahringer) writes:
> In article <················@naggum.net>, Erik Naggum <····@naggum.net> wrote:
> >
> >(defun permutations (list)
> > (if (cdr list)
> > (loop with rotation = list
> > do (setq rotation (nconc (last rotation) (nbutlast rotation)))
> > nconc (loop for list in (permutations (rest rotation))
> > collect (cons (first rotation) (copy-list list)))
> > until (eq rotation list))
> > (list list)))
> >
>
> Most likely this will work in all implementations, but it is not
> guaranteed to do so. You would need to test (equal rotation list),
> as nbutlast *may* modify its argument, but it does not have to.
My reading of the CLHS is that *may* is used because there are cases
where the original list aren't modified (e.g. n less than length of list),
but it seems fairly definitive in how NBUTLAST must work in normal cases:
"It changes the cdr of the cons n+1 from the end of the list to nil."
> Also memory-consumption could be reduced by replacing
> (copy-list list) simply with list, thereby allowing permutations
> to share common suffixes.
>
The COPY-LIST is required because list/rotation is destructively modified.
I double checked your assertion in LWW4.1 and the first permutation I get
with your modification is several elements too long.
> And of course I had to do a slightly modified version as well :-)
>
> (defun permutations (list)
> (if (cdr list)
> (loop for point on list
> nconc
> (prog2 (rotatef (first list) (first point))
> (loop for l1 in (permutations (rest list))
> collect
> (cons (first list) l1))
> (rotatef (first list) (first point))))
> (list (copy-list list))))
>
> cheers, Bernhard
> --
> --------------------------------------------------------------------------
> Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
> G1.25, 838 4041, ········@cs.waikato.ac.nz
> --------------------------------------------------------------------------
From: Reini Urban
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <39e1f967.789440835@judy>
Erik Naggum wrote:
>| The next step, i guess, would be to write a macro
>| with-all-permutations, which would take a list and a block, and run
>| that block once for each of the permutations of the list. But i
>| can't see how to do that without first going through the whole
>| process of generating all the permutations...
>
> Pass in a function call, wrap the macro body in a lambda, and off
> you go. Remember to do this only at the top-level call, and default
> to some innocuous function like identity.
I'd rather use a nth-permutation alike function, which I only wrote for
AutoLISP so far. (can be made much faster for CL of course. perm as
vector)
with this machinery you can avoid precalculating all permutations in
advance. doesn't series have such a beast also?
;;;----------------------------------------------------------------------
;;; Return the nth permutatation of a list.
;;; written by Reini Urban, based on perl code by Marc Jason Dominus
;;; (nth-permutation 0 '(a b c)) => (a b c))
;;; (nth-permutation 1 '(a b c)) => (a c b))
;;;----------------------------------------------------------------------
(defun NTH-PERMUTATION (i _l)
;; straightforward and slow would be
;(nth i (permutate l))
;; but we can do much better...
;;;(if (> 0 i (factorial len))
;;; (std-error "index out of range"))
(mapcar (function (lambda (j) (nth j _l)))
(nth-permutation-i i (length _l))))
;;; return the n-th permutated integer list (0 1 2 3 ...)
;;; (mapcar '(lambda (i) (nth-permutation-i i 3))
;;; (std-int-list (factorial 3)))
;;; => ((2 1 0) (1 2 0) (2 0 1) (0 2 1) (1 0 2) (0 1 2))
(defun NTH-PERMUTATION-I (n len / src pat perm)
(setq pat (nth-%permutation-pat n len))
(setq src (std-int-list len)) ; (0 1 2 .. len-1)
(while pat
(setq perm (cons (nth (car pat) src) perm)
src (std-delpos (car pat) src) ; delpos is slow
pat (cdr pat)))
perm)
;;; some magic numeric...
;;;(NTH-%PERMUTATION-PAT 0 3) (0 0 0)
;;;(NTH-%PERMUTATION-PAT 1 3) (0 1 0)
;;;(NTH-%PERMUTATION-PAT 2 3) (1 0 0)
;;;(NTH-%PERMUTATION-PAT 3 3) (1 1 0)
;;;(NTH-%PERMUTATION-PAT 4 3) (2 0 0)
;;;(NTH-%PERMUTATION-PAT 5 3) (2 1 0)
(defun NTH-%PERMUTATION-PAT (n len / i l)
(setq i 1)
(while (<= i len)
(setq l (cons (rem n i) l)
n (/ n i)
i (1+ i)))
l)
most functions are obvious, only std-delpos is weird: delete at
position, like (setf nth). while is in graham e.g.
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
From: Mark-Jason Dominus
Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
Date:
Message-ID: <39e93b5f.1ce6$51@news.op.net>
In article <··················@judy>,
Reini Urban <······@sbox.tu-graz.ac.at> wrote:
>;;; written by Reini Urban, based on perl code by Marc Jason Dominus
My name is Mark-Jason Dominus.
The Glauber <··········@my-deja.com> wrote:
>...
>The next step, i guess, would be to write a macro with-all-permutations,
>which would take a list and a block, and run that block once for
>each of the permutations of the list. But i can't see how to do that
>without first going through the whole process of generating all the
>permutations...
>
>
>Thanks for any insights.
Hello,
Very interesting is the technique of delayed evaluation as described in
SICP (Abelson and Sussman book). This allows to represent a infinite
sequence of values as a 'stream'. A stream is a partial construction of the
values to be accessed. The stream construction is incremented on demand, to
produce what it is needed (no more).
here is a CL implementation I have made about 10 years ago, with function
to compute permutations. At that time, I have found this very useful to
implement heuristic search algorithms where part of the data was very large
sequences.
(defstruct (lazy (:conc-name L_))
(fun nil :type function)
(arglist nil :type list))
(defun force (lazy)
(apply (L_fun lazy) (L_arglist lazy)))
(defun normalize (stream)
(cond ((null stream) nil)
((lazy-p (car stream))
(normalize (append (force (car stream))
(cdr stream))))
(T stream)))
;;; lazy car
(defun lar (stream)
(car stream))
;;; lazy cdr
(defun ldr (stream)
(normalize (cdr stream)))
(defun L_first (n stream)
(cond ((= n 0) nil)
((null stream) nil)
(t (cons (lar stream)
(L_first (1- n)
(ldr stream))))))
(defun L_enumerate-integers (m n)
(cond ((> m n) nil)
(t (list m (make-lazy :fun #'L_enumerate-integers
:arglist (list (1+ m) n))))))
(defun L_mapcar (f stream)
(cond ((null stream) nil)
(t (list (funcall f (lar stream))
(make-lazy :fun #'L_mapcar
:arglist (list f (ldr stream)))))))
(defun L_mapcan (f stream)
(normalize
(cond ((null stream) nil)
(t (nconc (funcall f (lar stream))
(list (make-lazy :fun #'L_mapcan
:arglist (list f (ldr stream)))))))))
(defun L_permutations (set)
(cond ((null set) (list NIL))
(T (L_mapcan #'(lambda (x)
(L_mapcar #'(lambda (p) (cons x p))
(L_permutations (remove x set))))
set))))
;; Example
(setf lazy_p (l_permutations '(1 2 3)))
(L_first 3 lazy_p)
;;;> ((1 2 3) (1 3 2) (2 1 3))
(defmacro L_pop (place)
`(when ,place
(setf ,place (ldr ,place))
(lar ,place)))
(L_pop lazy_p)
;;;> (1 3 2)
(L_pop lazy_p)
;;;> (2 1 3)
(L_pop lazy_p)
;;;> (2 3 1)
--
Francis Leboutte
www.algo.be +32-(0)4.388.39.19