Can someone tell me how to impliment a function power set of
a set in Common Lisp.
The power set of eg. '(a b c) is
'((a b c) (a b) (a c) (b c) (a) (b) (c) nil)
It should work for any number of elements in a set.
Thanx
Jonavan
In article <··········@itu1.sun.ac.za> ········@cs.sun.ac.za "J Jacobs" writes:
> Can someone tell me how to impliment a function power set of
> a set in Common Lisp.
> The power set of eg. '(a b c) is
> '((a b c) (a b) (a c) (b c) (a) (b) (c) nil)
> It should work for any number of elements in a set.
I'm no Lisp programmer but you just need to think how to do it
recursively. To work through your example...
To get the power set of '(a b c), you could start with
the power set of '(b c). You are allowed to think like this
when writing recursive functions. This gives you
'((b c) (b) (c) nil)
Now if you made a copy of that with 'a added into each member, you get
'((a b c) (a b) (a c) (a))
Join those together and
'((a b c) (a b) (a c) (a) (b c) (b) (c) nil)
Which is right unless the order is important to you.
The recursion terminates because the power set of nil is (nil).
BTW I suspect there is a neater, more efficient way but this
makes the thought process clear.
--
Pete Ward
Mondas IT Ltd
[J Jacobs]
| Can someone tell me how to impliment a function power set of
| a set in Common Lisp.
| The power set of eg. '(a b c) is
| '((a b c) (a b) (a c) (b c) (a) (b) (c) nil)
| It should work for any number of elements in a set.
what is the difference between (power '(b c)) and (power '(a b c))?
this should allow you to make a recursive definition, and ... voila!
#<Erik>
--
miracle of miracles. look what the Net dragged in.
If you use Screamer the power set of a set can be defined as follows:
(defun a-subset-of (x)
(if (null x)
nil
(let ((y (a-subset-of (rest x)))) (either (cons (first x) y) y))))
(defun powerset (x) (all-values (a-subset-of x)))
Screamer is available from ftp.cs.toronto.edu:/pub/qobi/screamer.tar.Z.
Jeff (home page http://www.cdf.toronto.edu/DCS/Personal/Siskind.html)
--
Jeff (home page http://www.cdf.toronto.edu/DCS/Personal/Siskind.html)