The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 |
Newsgroups: comp.lang.scheme
From: m...@gustavus.edu (Max Hailperin)
Date: 10 Jan 2002 11:53:13 -0800
Local: Thurs, Jan 10 2002 2:53 pm
Subject: Re: Subsets of a list
George Caswell <tetsu...@maine.rr.com> wrote in message <news:Pine.LNX.3.96.1020110005414.7936B-100000@adamant.homeworlds.net>... ... [tree-recursive procedure to find subsets of size n from a list, l] > The basic problem here is that certain subsets are being calculated more Actually, there is no big efficiency gain to be had in this case, > than once: ...[comparison with tree-recursive fib]... because the list that is the result is of length C(|l|, n), so it is inevitable that any procedure for consing up that list will take time of that order -- all that you can do is improve the constant factor. The big win, through dynamic programming or memoization, is only possible if the problem is changed to something like counting how many subsets there are. You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
| |||||||||||||