【練習】順列、組み合わせを Scheme で定義する

Scheme の練習中。

;; 階乗 n!
;; n! = n(n - 1)(n - 2)...3 x 2 x 1
;; ただし、0! = 1
(define (fact n)
    (cond [(or (zero? n) (= n 1)) 1]
        [else (* n (fact (- n 1)))]))




;; 順列: 異なるn個のものからr個を取り出して、１列に並べる並べ方の数
;; nPr = n!/(n - r)!
(define (P n r)
    (/ (fact n) (fact (- n r))))




;; 組み合わせ: 異なるn個のものからr個を取り出す選び方の数
;; nCr = nPr/r! = n!/r!(n-r)!
(define (C n r)
    (cond [(zero? r) 1]
        [else (/ (P n r) (fact r))]))




;; 異なるn個のものから重複を許してr個を取り出す組み合わせの数
;; nHr = (n + r - 1)Cr
(define (H n r)
    (C (- (+ n r) 1) r)) 

ちなみにそもそも、

;; すべてが異なる要素で構成された集合か
(define (set? lst)
    (cond [(null? lst) #t]
        [(member (car lst) (cdr lst)) #f]
        [else (set? (cdr lst))]))

#Scheme #Gauche #lisp

SN 2013/06/26 23:16:22

Archives > 20130619082645_scheme_memo1.html