1 --- a/src/scheme/L-99.scm Tue Jul 22 11:00:44 2008 +0000
2 +++ b/src/scheme/L-99.scm Tue Jul 22 15:07:57 2008 +0000
3 @@ -459,3 +459,30 @@
4 (if (null? lst)
5 '()
6 (rnd-select lst (element-num lst))))
7 +
8 +;; P26 - Generate the combinations of K distinct objects chosen from
9 +;; the N elements of a list.
10 +;;
11 +;; In how many ways can a committee of 3 be chosen from a group of 12
12 +;; people? We all know that there are C(12,3) = 220 possibilities
13 +;; (C(N,K) denotes the well-known binomial coefficients). For pure
14 +;; mathematicians, this result may be great. But we want to really
15 +;; generate all the possibilities in a list.
16 +;;
17 +;; > Example:
18 +;; (combination 3 '(a b c d e f))
19 +;; ((a b c) (a b d) (a b e) ... )
20 +
21 +;; C(m, n) = C(m-1, n-1) + C(m-1, n)
22 +;; C(n, n) = 1
23 +;; C(m, 1) = m
24 +
25 +(define (combination num lst)
26 + (define (iter num lst sublist)
27 + (cond ((eq? num 0) (list sublist))
28 + ((eq? num (element-num lst)) (list (append sublist lst)))
29 + (else
30 + (append (iter (- num 1) (cdr lst) (append sublist (list (car lst))))
31 + (iter num (cdr lst) sublist)))))
32 +
33 + (iter num lst '()))