combinations.scm

30分プログラム。その32。

util.combinationsの再実装。ネタに困ったら車輪を再発明すればいいんだ。

;; 組み合わせ
gosh> (print (combination 2 '(a b c)))
((a b) (a c) (b c))
 
;; 順列
gohs> (perm '(a b c))
((c b a) (c a b) (b a c) (b c a) (a c b) (a b c))

(use srfi-1)
(define (circle lst)
  (let1 c-lst (apply circular-list lst)
	(list-tabulate 
	 (length lst)
	 (lambda(i) (take (drop c-lst i)
			  (length lst))))))
 
(define (perm lst)
  (if (null? lst)
      '(())
      (fold (lambda(item result)
	      (append (add-top (car item) (perm (cdr item)))
		      result))
	    '()
	    (circle lst))))
  
(define (add-top x lst)
  (map (lambda(item) (cons x item)) lst))
   
(define (combination n lst)
  (cond ((= (length lst) n) (list lst))
	((= n 0) '(()))
	(else
	 (append (add-top (car lst)
			  (combination (- n 1) (cdr lst)))
		 (combination n (cdr lst))))))