Newsgroups: comp.lang.scheme
From: Al Gore Rhythm Petrofsky <al-gore-rhy...@petrofsky.org>
Date: 17 Jan 2002 01:59:26 -0800
Local: Thurs, Jan 17 2002 4:59 am
Subject: Re: The FASTEST subsets function [Was: Subsets of a list]
Eli Barzilay <e...@barzilay.org> writes: I believe the minimum number of unique pairs in the result is > b...@cs.purdue.edu (Bradley J Lucier) writes: > > BTW, there are 184756 subsets of size 10 in a length-20 list set,, > > > (* 184756 (+ 12 (* 10 12))) > > bytes. > But what about lists that share parts (which most of it is)? 537471 = [ C(20,10) + C(19,9) + C(18,8) + ... + C(11,1) ] + C(20,10) where C(n,m) = n!/(m!n-m!). (The extra C(20,10) are the pairs 537471 is the number of conses done by the accumulator-based version: (define (subsets l n) You can save an additional whopping ten pairs by reusing parts of the (define (subsets l n) -al P.S. A drawback of the stream and memoization versions is that they 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.
| ||||||||||||||