ok, so i made it through the posts on my variations function (thanks!).
basically, i have the function: (variations 'x '(y z)) -> ((x y z) (y
x z) (y z x)). (see original post for the awesome solutions proposed to
this titled "simiple lisp function")
now, i was thinking i could use this function in a new function:
(permutations '(x y z)) -> ((x y z) (x z y) (y z x) (y x z) (z x y) (z y
x)) (not necessarily in that order, just all the permutations of the
given list).
i was thinking of writing a function that would continually take
variations on a certain, single list (like (x y z)), and then on the
results returned from that, and so on. Then check to see if each list
was already in some master list (starting out empty), and if not then
add it to the list. the end condition to stop the recursion would be
when the number of elements in the list equalled the factorial of the
length of the original list. ex. (x y z) will yield 6 permutations - 3!.
is this a good idea? after working a bit on paper it looked like i'd be
creating lots of duplicate lists that would ultimately be rejected.
i've seen other implementations of permutation, but i'd like to use my
function somehow (building on what i've done seems like a natural thing
to do). thanks in advance for any input!
kareem
Kareem Nutt <··········@gmail.com> writes:
> ok, so i made it through the posts on my variations function
> (thanks!). basically, i have the function: (variations 'x '(y z)) ->
> ((x y z) (y x z) (y z x)). (see original post for the awesome
> solutions proposed to this titled "simiple lisp function")
>
> now, i was thinking i could use this function in a new function:
> (permutations '(x y z)) -> ((x y z) (x z y) (y z x) (y x z) (z x y) (z
> y x)) (not necessarily in that order, just all the permutations of the
> given list).
The purpose of recursion in problems like these is to break the
problem down into a simpler one. What is a simpler problem than
(permutations '(x y z))? It is (permutations '(y z)) of course.
The simplest is (permuations '(z)), it simply returns ((Z)).
Now the rest is cut out: given the answer to the simpler problem, how
do you take one step up to a harder problem? How do you go from
(permutations '(y z)) to (permutations '(x y z))? Once you have this
figured out, you have the recursive answer.
Hint: Take a very close look at the output of (permutations '(y z))
and consider what would happen if you used VARIATIONS in a creative
way, on it.
--
;;;; Matthew Danish -- user: mrd domain: cmu.edu
;;;; OpenPGP public key: C24B6010 on keyring.debian.org
Kareem Nutt <··········@gmail.com> writes:
> ok, so i made it through the posts on my variations function
> (thanks!). basically, i have the function: (variations 'x '(y z)) ->
> ((x y z) (y x z) (y z x)). (see original post for the awesome
> solutions proposed to this titled "simiple lisp function")
>
> now, i was thinking i could use this function in a new function:
> (permutations '(x y z)) -> ((x y z) (x z y) (y z x) (y x z) (z x y) (z
> y x)) (not necessarily in that order, just all the permutations of the
> given list).
>
> i was thinking of writing a function that would continually take
> variations on a certain, single list (like (x y z)), and then on the
> results returned from that, and so on. Then check to see if each list
> was already in some master list (starting out empty), and if not then
> add it to the list. the end condition to stop the recursion would be
> when the number of elements in the list equalled the factorial of the
> length of the original list. ex. (x y z) will yield 6 permutations -
> 3!.
>
> is this a good idea? after working a bit on paper it looked like i'd
> be creating lots of duplicate lists that would ultimately be
> rejected. i've seen other implementations of permutation, but i'd like
> to use my function somehow (building on what i've done seems like a
> natural thing to do). thanks in advance for any input!
permutations has also a recursive definition!
(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))))));;variations
(defun permutations (elements)
(if (or (null elements) (null (cdr elements)))
(list elements)
(mapcan (lambda (subperm) (variations (car elements) subperm))
(permutations (cdr elements)))));;permutations
[49]> (permutations '())
(NIL)
[50]> (permutations '(a))
((a))
[51]>(permutations '(a b))
((A B) (B A))
[52]> (permutations '(a b c))
((A B C) (B A C) (B C A) (A C B) (C A B) (C B A))
[53]> (permutations '(a b c d))
((A B C D) (B A C D) (B C A D) (B C D A) (A C B D) (C A B D) (C B A D) (C B D A)
(A C D B) (C A D B) (C D A B) (C D B A) (A B D C) (B A D C) (B D A C) (B D C A)
(A D B C) (D A B C) (D B A C) (D B C A) (A D C B) (D A C B) (D C A B)
(D C B A))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.