Gmail Calendar Documents Reader Web more »
Recently Visited Groups | Help | Sign in
Google Groups Home
Message from discussion The FASTEST subsets function [Was: Subsets of a list]
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
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Al Gore Rhythm Petrofsky  
View profile  
 More options Jan 17 2002, 4:59 am
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:
> b...@cs.purdue.edu (Bradley J Lucier) writes:

> > BTW, there are 184756 subsets of size 10 in a length-20 list set,,
> > so in Gambit, which takes 12 bytes per cons cell, this takes

> > > (* 184756 (+ 12 (* 10 12)))
> > 24387792

> > bytes.

> But what about lists that share parts (which most of it is)?

I believe the minimum number of unique pairs in the result 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
connecting the subsets into a list.)  I'll leave the proof of this
claim as an exercise for Oleg.

537471 is the number of conses done by the accumulator-based version:

(define (subsets l n)
  (let ss ((l l) (len (length l)) (n n) (little-acc '()) (big-acc '()))
    (cond ((zero? n) (cons little-acc big-acc))
          ((> n len) big-acc)
          (else (ss (cdr l) (- len 1) (- n 1) (cons (car l) little-acc)
                    (ss (cdr l) (- len 1) n little-acc big-acc))))))

You can save an additional whopping ten pairs by reusing parts of the
argument.  I proclaim the following the STINGIEST subsets function
ever known to man:

(define (subsets l n)
  (let ss ((len (length l)) (n n) (little-acc '()) (big-acc '()))
    (cond ((zero? n) (cons little-acc big-acc))
          ((> n len) big-acc)
          (else (let ((last-pair (list-tail l (- len 1))))
                  (ss (- len 1) (- n 1)
                      (if (eq? (cdr last-pair) little-acc)
                          last-pair
                          (cons (car last-pair) little-acc))
                      (ss (- len 1) n little-acc big-acc)))))))

-al

P.S.  A drawback of the stream and memoization versions is that they
take a ridiculous amount of time to find all the length 18 subsets of
a 20 element list.


    Reply to author    Forward  
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.

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2009 Google