Hi, I know you guys probably get a lot of annoying posts for homework
help, but hey, I am desperate...
4. Write a Lisp function Subsets(A,B) that recursively generates the
set of all subsets of an arbitrary set S when B = S and A = ().
That is the assignment, I can not for the life of me figure out how to
do subsets! I can do stuff like finding the length of a list and etc,
but subsets just is impossible for me! >>PLEASE HELP ME<<
Thanks
In article <····························@posting.google.com>,
··········@hotmail.com (M.Y.Cool) wrote:
> Hi, I know you guys probably get a lot of annoying posts for homework
> help, but hey, I am desperate...
>
>
> 4. Write a Lisp function Subsets(A,B) that recursively generates the
> set of all subsets of an arbitrary set S when B = S and A = ().
>
> That is the assignment, I can not for the life of me figure out how to
> do subsets! I can do stuff like finding the length of a list and etc,
> but subsets just is impossible for me! >>PLEASE HELP ME<<
You might want to consider that a subset of the items in a list is just
a copy of the list with zero or more items left out.
paul
··········@hotmail.com (M.Y.Cool) writes:
(subset #'gist (quote
> That is the assignment, I can not for the life of me figure out how to
> do subsets! I can do stuff like finding the length of a list and etc,
> but subsets just is impossible for me! >>PLEASE HELP ME<<
))
=> (That I can not figure out how etc, just impossible for PLEASE ME)
(defun subset (predicate tokens)
(let ((yada nil))
(while tokens
(let ((tok (car tokens)))
(when (funcall predicate tok)
(setq yada (append yada (list tok)))))
(setq tokens (cdr tokens)))
yada))
;; of course, if you turn this in verbatim, you risk flames, academic
;; and otherwise, arising from availing yourself of the poor style and
;; willfully oblique (mis)interpretation of the question displayed...
;;
;; happy hacking, anyway.
;;
;; thi
On 28 Apr 2003 10:43:56 -0700, ··········@hotmail.com (M.Y.Cool)
wrote:
>Hi, I know you guys probably get a lot of annoying posts for homework
>help, but hey, I am desperate...
>
>
>4. Write a Lisp function Subsets(A,B) that recursively generates the
>set of all subsets of an arbitrary set S when B = S and A = ().
>
>That is the assignment, I can not for the life of me figure out how to
>do subsets! I can do stuff like finding the length of a list and etc,
>but subsets just is impossible for me! >>PLEASE HELP ME<<
>
Think recursively. Think mathematically.
Hint 1:
Suppose you have a set of N elements. Suppose 'a'
was an element of that set. Suppose you already had a way
of determining all the subsets of your set without element 'a'
(i.e, a set of N-1 elements, the same as your set, but without 'a').
Now how would you create all the subsets of your original set?
Hint 2:
What happens when you continue this process and you reach N=0 ?
"M.Y.Cool" <··········@hotmail.com> wrote in message
·································@posting.google.com...
> Hi, I know you guys probably get a lot of annoying posts for homework
> help, but hey, I am desperate...
>
>
> 4. Write a Lisp function Subsets(A,B) that recursively generates the
> set of all subsets of an arbitrary set S when B = S and A = ().
>
> That is the assignment, I can not for the life of me figure out how to
> do subsets! I can do stuff like finding the length of a list and etc,
> but subsets just is impossible for me! >>PLEASE HELP ME<<
>
> Thanks
The set of all subsets of a given set S is the power set P(S). For a
set S of length N, the power set has 2^N elements, including the empty
set. For example, if S has 20 elements the power set will have 2^20,
or more than 1,000,000, elements.
(defun power-set (set)
(let ((power-set (list ()))) ; power set always contains empty set
(labels
((insert (subset)
(loop for elt in set
until (eql elt (first subset))
collect (cons elt subset)))
(power-set-length-n (length-m-sets)
(mapcan #'(lambda (length-m-set)
(insert length-m-set))
length-m-sets))
(power-set-aux (length-m-sets)
;; n = m + 1
(unless (null length-m-sets)
(let ((length-n-sets (power-set-length-n length-m-sets)))
(setf power-set (append length-n-sets power-set))
(power-set-aux length-n-sets)))))
(power-set-aux power-set))
power-set))
> (power-set '(1 2 3))
((1 2 3) (1 2) (1 3) (2 3) (1) (2) (3) NIL)
Regards,
jag
"John Gilson" <···@acm.org> writes:
> "M.Y.Cool" <··········@hotmail.com> wrote in message
> ·································@posting.google.com...
> > Hi, I know you guys probably get a lot of annoying posts for homework
> > help, but hey, I am desperate...
> >
> >
> > 4. Write a Lisp function Subsets(A,B) that recursively generates the
> > set of all subsets of an arbitrary set S when B = S and A = ().
> >
> > That is the assignment, I can not for the life of me figure out how to
> > do subsets! I can do stuff like finding the length of a list and etc,
> > but subsets just is impossible for me! >>PLEASE HELP ME<<
> >
> > Thanks
>
> The set of all subsets of a given set S is the power set P(S). For a
> set S of length N, the power set has 2^N elements, including the empty
> set. For example, if S has 20 elements the power set will have 2^20,
> or more than 1,000,000, elements.
this is good
>
> (defun power-set (set)
> (let ((power-set (list ()))) ; power set always contains empty set
> (labels
> ((insert (subset)
> (loop for elt in set
> until (eql elt (first subset))
> collect (cons elt subset)))
> (power-set-length-n (length-m-sets)
> (mapcan #'(lambda (length-m-set)
> (insert length-m-set))
> length-m-sets))
> (power-set-aux (length-m-sets)
> ;; n = m + 1
> (unless (null length-m-sets)
> (let ((length-n-sets (power-set-length-n length-m-sets)))
> (setf power-set (append length-n-sets power-set))
> (power-set-aux length-n-sets)))))
> (power-set-aux power-set))
> power-set))
>
> > (power-set '(1 2 3))
> ((1 2 3) (1 2) (1 3) (2 3) (1) (2) (3) NIL)
this is too good, you gave too much help IMO.
>
> Regards,
> jag
I thought the idea was to help the student figure out the problem.
marc
"Marc Spitzer" <········@optonline.net> wrote in message
···················@bogomips.optonline.net...
> "John Gilson" <···@acm.org> writes:
>
> > "M.Y.Cool" <··········@hotmail.com> wrote in message
> > ·································@posting.google.com...
> > > Hi, I know you guys probably get a lot of annoying posts for homework
> > > help, but hey, I am desperate...
> > >
> > >
> > > 4. Write a Lisp function Subsets(A,B) that recursively generates the
> > > set of all subsets of an arbitrary set S when B = S and A = ().
> > >
> > > That is the assignment, I can not for the life of me figure out how to
> > > do subsets! I can do stuff like finding the length of a list and etc,
> > > but subsets just is impossible for me! >>PLEASE HELP ME<<
> > >
> > > Thanks
> >
> > The set of all subsets of a given set S is the power set P(S). For a
> > set S of length N, the power set has 2^N elements, including the empty
> > set. For example, if S has 20 elements the power set will have 2^20,
> > or more than 1,000,000, elements.
>
> this is good
>
> >
> > (defun power-set (set)
> > (let ((power-set (list ()))) ; power set always contains empty set
> > (labels
> > ((insert (subset)
> > (loop for elt in set
> > until (eql elt (first subset))
> > collect (cons elt subset)))
> > (power-set-length-n (length-m-sets)
> > (mapcan #'(lambda (length-m-set)
> > (insert length-m-set))
> > length-m-sets))
> > (power-set-aux (length-m-sets)
> > ;; n = m + 1
> > (unless (null length-m-sets)
> > (let ((length-n-sets (power-set-length-n length-m-sets)))
> > (setf power-set (append length-n-sets power-set))
> > (power-set-aux length-n-sets)))))
> > (power-set-aux power-set))
> > power-set))
> >
> > > (power-set '(1 2 3))
> > ((1 2 3) (1 2) (1 3) (2 3) (1) (2) (3) NIL)
>
> this is too good, you gave too much help IMO.
Possibly, but this is how I considered the situation. If the same honesty
that led the original poster to declare this a homework problem up front
prevails, he'll hopefully ignore the solution initially and focus on the strong hints
given by others while he still believes his eureka moment is at hand. Other
interested readers might dive directly into the code. However, if the OP is truly
at a loss, as he alludes, and the hints prove inadequate, he could always resort to
studying a solution which might provide enlightenment for both this and other
similar problems, perhaps on the very same homework assignment, undoubtedly
during exams.
Either way, he'll surely be on his own come exam time. So either he's been
helped in preparation for that day, granted, maybe excessively, or that day
of reckoning will mete out its own unavoidable judgment. Reminds me of
back in the day taking SICP and, if memory serves, problem sets being
worth a whopping 10% of the grade, the remaining 90% were exams.
I guess that experience has had a deeper effect than I care to admit. :)
> > Regards,
> > jag
>
> I thought the idea was to help the student figure out the problem.
>
> marc
"John Gilson" <···@acm.org> writes:
> "Marc Spitzer" <········@optonline.net> wrote in message
> >
> > this is too good, you gave too much help IMO.
>
> Possibly, but this is how I considered the situation. If the same
> honesty that led the original poster to declare this a homework
> problem up front prevails, he'll hopefully ignore the solution
> initially and focus on the strong hints given by others while he
> still believes his eureka moment is at hand. Other interested
I do not think this is fair to the student, here is the answer just do
not look at it. And you did not clearly lable it as a answer so he
could accadently cheat.
> readers might dive directly into the code. However, if the OP is
> truly at a loss, as he alludes, and the hints prove inadequate, he
> could always resort to studying a solution which might provide
> enlightenment for both this and other similar problems, perhaps on
> the very same homework assignment, undoubtedly during exams.
I think there is a big difference between a rough guided tour of the
algorithm, this is what it does and how it works, and a packaged
solution. One of the big problem with answers is that they do not
take you through the process of solving the problem. From a learning
POV the correct answer is besides the point, figuring out how to come
up with a repeatable method for solving related problems is the
point. actually solving or at least implementing in lisp from an
algorithm would be much more useful on related problems, the method
is important, the specific result is not. I have told students in
classes that I was a teaching assistant in I grade work out of 10
points an answer was worth at most 2. The method is what is what is
important it is what stays with you and you can build upon it for the
next more complex problem.
I honestly am offended by the fact that you think that because he may
be screwed on his test because of your deliberate action of doing his
homework for him when he was honest enough to ask for help doing it
himself, especially when you did not label it as an answer instead of
the help he asked for.
>
> Either way, he'll surely be on his own come exam time. So either
> he's been helped in preparation for that day, granted, maybe
> excessively, or that day of reckoning will mete out its own
> unavoidable judgment. Reminds me of back in the day taking SICP
> and, if memory serves, problem sets being worth a whopping 10% of
> the grade, the remaining 90% were exams. I guess that experience
> has had a deeper effect than I care to admit. :)
You do not know what the breakdown of his course is. You see my root
problem here is that he acted in good faith, help me figure this
homework problem out. And you did not act in good faith in return,
you gave an answer with out any explanation(remember you also did not
label it as not help) and you then say it is ok because if he uses my
answer he will be screwed on the test. What did he do to you to
warrant such treatment on your part?
marc
>
> > > Regards,
> > > jag
> >
> > I thought the idea was to help the student figure out the problem.
> >
> > marc
"Marc Spitzer" <········@optonline.net> wrote in message
···················@bogomips.optonline.net...
> "John Gilson" <···@acm.org> writes:
>
> > "Marc Spitzer" <········@optonline.net> wrote in message
> > >
> > > this is too good, you gave too much help IMO.
> >
> > Possibly, but this is how I considered the situation. If the same
> > honesty that led the original poster to declare this a homework
> > problem up front prevails, he'll hopefully ignore the solution
> > initially and focus on the strong hints given by others while he
> > still believes his eureka moment is at hand. Other interested
>
> I do not think this is fair to the student, here is the answer just do
> not look at it. And you did not clearly lable it as a answer so he
> could accadently cheat.
>
> > readers might dive directly into the code. However, if the OP is
> > truly at a loss, as he alludes, and the hints prove inadequate, he
> > could always resort to studying a solution which might provide
> > enlightenment for both this and other similar problems, perhaps on
> > the very same homework assignment, undoubtedly during exams.
>
> I think there is a big difference between a rough guided tour of the
> algorithm, this is what it does and how it works, and a packaged
> solution. One of the big problem with answers is that they do not
> take you through the process of solving the problem. From a learning
> POV the correct answer is besides the point, figuring out how to come
> up with a repeatable method for solving related problems is the
> point. actually solving or at least implementing in lisp from an
> algorithm would be much more useful on related problems, the method
> is important, the specific result is not. I have told students in
> classes that I was a teaching assistant in I grade work out of 10
> points an answer was worth at most 2. The method is what is what is
> important it is what stays with you and you can build upon it for the
> next more complex problem.
>
> I honestly am offended by the fact that you think that because he may
> be screwed on his test because of your deliberate action of doing his
> homework for him when he was honest enough to ask for help doing it
> himself, especially when you did not label it as an answer instead of
> the help he asked for.
>
> >
> > Either way, he'll surely be on his own come exam time. So either
> > he's been helped in preparation for that day, granted, maybe
> > excessively, or that day of reckoning will mete out its own
> > unavoidable judgment. Reminds me of back in the day taking SICP
> > and, if memory serves, problem sets being worth a whopping 10% of
> > the grade, the remaining 90% were exams. I guess that experience
> > has had a deeper effect than I care to admit. :)
>
> You do not know what the breakdown of his course is. You see my root
> problem here is that he acted in good faith, help me figure this
> homework problem out. And you did not act in good faith in return,
> you gave an answer with out any explanation(remember you also did not
> label it as not help) and you then say it is ok because if he uses my
> answer he will be screwed on the test. What did he do to you to
> warrant such treatment on your part?
>
> marc
Forgive my en masse response to your point-by-point comments.
If one's aim is simply to acquire solutions quickly and easily with no
intent to learn, there is usually ample opportunity. Since there's
no obvious reason to assume the original poster is stupid or
intellectually dishonest, to the contrary there's evidence to conclude
otherwise, one would hope, with reason, that he will make the right
personal choice so as to not cheat himself out of a learning
experience while ensuring there is indeed such an experience and not
just abject frustration which might lead to unfortunate and hastily
arrived at conclusions about one's abilities or the subject matter.
If he chooses to use the earlier provided hints, then one trusts he
will do so instead of studying my solution or availing himself of
alternate quick fixes, e.g., digging up old problem set solutions,
getting it from a classmate, or searching the Web. If after scanning
the hints he still finds himself lost, or after solving the problem
himself he's interested in another's solution, he might choose to
peruse my offering. Should the solution be explicitly marked as such?
It probably should, however, a quick scan of the code should
immediately reveal that without further comment. Will a quick cursory
glance of said solution provide an epiphany? I think not, there's
still work to be done in working through the code and gleaning from it
the algorithm employed, probably not a trivial undertaking for a
student new to the subject. Exactly why prose was not provided, just
code. "Accidental cheating" would seem improbable. One of the useful
pedagogical techniques used in SICP is providing the bulk of the code for a
solution where just a few small snippets must be filled in. Perhaps this might
have been a better compromise between hints and a total solution? Possibly!
Was my intent to screw the student by leaving him intellectually crippled
for his exams? Of course not, but the onus of test taking might very
well guide him in making his choice and, yes, it still remains completely
his choice.
Regards,
jag
> > > I thought the idea was to help the student figure out the problem.
> > >
> > > marc
"Marc Spitzer" <········@optonline.net> wrote in message
···················@bogomips.optonline.net...
> "John Gilson" <···@acm.org> writes:
> I honestly am offended by the fact that you think that because he may
Aren't you usually the one telling all us other "moral policemen" that being
offended is our own problem?
> > Either way, he'll surely be on his own come exam time. So either
> > he's been helped in preparation for that day, granted, maybe
> > excessively, or that day of reckoning will mete out its own
> > unavoidable judgment. Reminds me of back in the day taking SICP
> > and, if memory serves, problem sets being worth a whopping 10% of
> > the grade, the remaining 90% were exams. I guess that experience
> > has had a deeper effect than I care to admit. :)
>
> You do not know what the breakdown of his course is. You see my root
> problem here is that he acted in good faith, help me figure this
Well that's just it, isn't it. It's your problem.
Don't forget, most professors are not such idiots that they would not wonder
at a lisp newbie who "can do stuff like finding the length of a list"
handing in John's solution as is. And untangling the LABELS and MAPCAN
#'(LAMBDA..)'s might just be an excellent way of coming to grips with the
algorithm at hand.
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
"Coby Beck" <·····@mercury.bc.ca> writes:
> "Marc Spitzer" <········@optonline.net> wrote in message
> ···················@bogomips.optonline.net...
> > "John Gilson" <···@acm.org> writes:
> > I honestly am offended by the fact that you think that because he may
>
> Aren't you usually the one telling all us other "moral policemen" that being
> offended is our own problem?
yes it is my own problem and from your response it is yours also. But
when some student actually says this it homework, means do not do my
homework for me, and someone else deliberately post the solution, with
out even bothering to mark it as a solution, I know that is a gross
disservice to the student. Then to follow it up with, if he uses my
answer with out figuring it out for him self he will get his on the
test, or it not my fault if I made it possible for him to not
understand what is going on because if he was a good student he would
not use it anyway. This is wrong.
>
> > > Either way, he'll surely be on his own come exam time. So either
> > > he's been helped in preparation for that day, granted, maybe
> > > excessively, or that day of reckoning will mete out its own
> > > unavoidable judgment. Reminds me of back in the day taking SICP
> > > and, if memory serves, problem sets being worth a whopping 10% of
> > > the grade, the remaining 90% were exams. I guess that experience
> > > has had a deeper effect than I care to admit. :)
> >
> > You do not know what the breakdown of his course is. You see my root
> > problem here is that he acted in good faith, help me figure this
>
> Well that's just it, isn't it. It's your problem.
Its my problem the student acted in good faith? ok, I can live with
that. So who gets all the do my homework for me people?
>
> Don't forget, most professors are not such idiots that they would not wonder
> at a lisp newbie who "can do stuff like finding the length of a list"
> handing in John's solution as is. And untangling the LABELS and MAPCAN
> #'(LAMBDA..)'s might just be an excellent way of coming to grips with the
> algorithm at hand.
Ah so John was seting him up to get nailed for cheating, thaks for
clearing that up. You are right that is very helpful. How could
I miss that.
marc
M.Y.Cool wrote:
> Hi, I know you guys probably get a lot of annoying posts for homework
> 4. Write a Lisp function Subsets(A,B) that recursively generates the
> set of all subsets of an arbitrary set S when B = S and A = ().
I'll toss out a suggestion in case it helps you:
Start by writing a function that, given an empty set (how are you going
to represent sets, by the way?), returns all the subsets of an empty set.
Then, write another function that, given a set with one element, returns
all the subsets.
Then, write another function that, given a set with two elements,
returns all the subsets.
Etc.
-- Frank