Hi all,
I'm quite new to Lisp, and confusing myself thoroughly.
I'm attempting to implement an Erlang function in Lisp; for those who
know it, it's
permutations([]) -> [[]];
permutations(L) ->
[[H|T] || H <- L, T <- permutations(L--[H]).
For a given sequence, it will generate all permutations of it.
So far, and this is just on paper, mind, so it will have some terrible
flaws, I've come up with this - http://paste.lisp.org/display/27871
I think I need to use one of the map functions, but I don't know whcih
one or how to use it. Can anyone recommend a good Lisp function to
generate all permutations of a given sequence?
Regards,
Liam Clarke
Okay, I just realised that the biggest flaw is using T as a variable
name. Disregard that....
On Oct 13, 3:54 pm, ···········@gmail.com" <··········@gmail.com>
wrote:
> Hi all,
>
> I'm quite new to Lisp, and confusing myself thoroughly.
> I'm attempting to implement an Erlang function in Lisp; for those who
> know it, it's
>
> permutations([]) -> [[]];
> permutations(L) ->
> [[H|T] || H <- L, T <- permutations(L--[H]).
>
> For a given sequence, it will generate all permutations of it.
>
> So far, and this is just on paper, mind, so it will have some terrible
> flaws, I've come up with this -http://paste.lisp.org/display/27871
>
> I think I need to use one of the map functions, but I don't know whcih
> one or how to use it. Can anyone recommend a good Lisp function to
> generate all permutations of a given sequence?
>
> Regards,
>
> Liam Clarke
···········@gmail.com" <··········@gmail.com> writes:
> Hi all,
>
> I'm quite new to Lisp, and confusing myself thoroughly.
> I'm attempting to implement an Erlang function in Lisp; for those who
> know it, it's
>
> permutations([]) -> [[]];
> permutations(L) ->
> [[H|T] || H <- L, T <- permutations(L--[H]).
A direct translation will be:
(defun permutations (list)
(if (endp list)
'(())
(mapcan (lambda (head)
(mapcar (lambda (tail) (cons head tail))
(permutations (remove head list))))
list)))
(permutations '(a b c))
--> ((A B C) (A C B) (B A C) (B C A) (C A B) (C B A))
MAPCAN is like MAPCAR, but it concatenate (with NCONC) the resulting
lists instead of accumulating in a list like MAPCAR.
But this is not a good function, because REMOVE is O(n). Using an
auxiliary function to build the variations:
(variations 'x '(a b c))
--> ((X A B C) (A X B C) (A B X C) (A B C X))
we can implement permutations slightly more efficiently, both in time
and space;
(defun variations (item list)
(if (null list)
(list (list item))
(cons (cons item list)
(mapcar (lambda (rest) (cons (car list) rest))
(variations item (cdr list))))))
(defun permutationsv (elements)
(cond
((null elements) (list elements))
((null (cdr elements)) (list elements))
(t (mapcan (lambda (subperm) (variations (car elements) subperm))
(permutationsv (cdr elements))))))
[362]> (time (length (permutations '(a b c d e f g h))))
Real time: 0.514136 sec.
Run time: 0.464029 sec.
Space: 5599328 Bytes
GC: 2, GC time: 0.144009 sec.
40320
[364]> (time (length (permutationsv '(a b c d e f g h))))
Real time: 0.138536 sec.
Run time: 0.140008 sec.
Space: 3272888 Bytes
GC: 1, GC time: 0.064003 sec.
40320
[365]>
Commenting your lisp code:
(defun permutations(L h-list acc)
(cond
((null h-list) acc)
(t
(let ((H (car h-list))
(new-L (remove H L)))
(setf T (permutations new-L new-L acc))
(setf acc (concatenate 'list acc (recurse-tail H T nil)))
(permutations L (cdr h-list) acc)))))
1- use names instead of 1-letter acronyms.
2- use endp, first and rest when you work on list instead of on
low-level cons cells.
3- don't use SETF, use LET instead.
4- don't use SETF or LET, if the variable is referenced once, you can
just insert the expression where it's used. (Ok, don't overdo it,
like in a 60-line function, but in a seven-line function, there's
no problem).
5- CONCATENATE will copy all the arguments. APPEND copies all but the
last. NCONC copy none. In this case, you're accumulating elements to acc,
which is a list you are building so you can use NCONC.
6- When there is only one test in COND, it might be better to use IF.
7- NIL = false.
'NIL = symbol named "NIL".
() = empty list as code, eg. (defun f () 'no-argument)
'() = empty list as data.
So here is what it could look like, if it worked anyways:
(defun permutations(list head-list acc)
(if (endp head-list)
acc
(let ((head (first head-list))
(new-list (remove head list)))
(permutations list
(rest head-list)
(nconc acc
(recurse-tail head
(permutations new-list new-list acc)
'()))))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
WARNING: This product attracts every other piece of matter in the
universe, including the products of other manufacturers, with a
force proportional to the product of the masses and inversely
proportional to the distance between them.