Google Groups Home
Help | Sign in
Message from discussion 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
oleg@pobox.com  
View profile
 More options Jan 9 2002, 8:37 pm
Newsgroups: comp.lang.scheme
From: o...@pobox.com (o...@pobox.com)
Date: 9 Jan 2002 17:37:11 -0800
Local: Wed, Jan 9 2002 8:37 pm
Subject: Re: Subsets of a list

baruc...@libertysurf.france (Thomas Baruchel) wrote in message <news:a1hqr0$slp$2@wanadoo.fr>...
> it takes a list and an integer as arguments and returns a list of lists
> which are all different subsets of length n from the given list:
> (subset '(1 2 3 4) 2)
> --> ((1 2) (1 3) (1 4) (2 3) ( 2 4) (3 4))

Let's consider the mathematical definition of this function:

subset '() n ==> '() : there are no subsets in an empty set
subset l 0   ==> '(()): the only subset of size (cardinality 0) is an
                  empty set

subset (a . tail) n ==> { (a . x) | x <- subset tail (n-1) } Union
                        subset tail n
that is, subsets of size n will either contain the element a, or will
not contain it.

This mathematical definition directly translates to Scheme.

(define (subset l n)
  (cond
   ((<= n 0) '(()))
   ((null? l) '())
   ((= n 1) (map list l))
   (else
    (append
     (let ((hd (car l)))
       (map
        (lambda (lst) (cons hd lst))
        (subset (cdr l) (- n 1))))
     (subset (cdr l) n)))))

The solution is purely functional.

Note, the code has an optimization for the case n=1, in which case the
answer is a set of all singleton subsets.

Example:

(display (subset '(1 2 3 4) 0))
===> (())

(display (subset '(1 2 3 4) 1))
===> ((1) (2) (3) (4))

(display (subset '(1 2 3 4) 2))
===> ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))

(display (subset '(1 2 3 4) 3))
===> ((1 2 3) (1 2 4) (1 3 4) (2 3 4))

(display (subset '(1 2 3 4) 4))
===> ((1 2 3 4))

(display (subset '(1 2 3 4) 5))
===> ()

The cardinalities of the answers above form the Pascal triangle, btw.


    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
©2008 Google