Newsgroups: comp.lang.scheme
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>... Let's consider the mathematical definition of this function: > 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)) subset '() n ==> '() : there are no subsets in an empty set subset (a . tail) n ==> { (a . x) | x <- subset tail (n-1) } Union This mathematical definition directly translates to Scheme. (define (subset l n) The solution is purely functional. Note, the code has an optimization for the case n=1, in which case the Example: (display (subset '(1 2 3 4) 0)) (display (subset '(1 2 3 4) 1)) (display (subset '(1 2 3 4) 2)) (display (subset '(1 2 3 4) 3)) (display (subset '(1 2 3 4) 4)) (display (subset '(1 2 3 4) 5)) The cardinalities of the answers above form the Pascal triangle, btw. 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.
| ||||||||||||||