星期日, 4月 15, 2012

求出n取k組合的列表 Lisp版

廢話就不多說了,這次改寫Lisp版本的求組合列表,由於太久沒寫,著實吃了不少苦頭。由於Lisp版本眾,我本來想用Emacs開發,可是我把Emacs的hotkey全忘光了,只記得c-x c-e,後來就改用GNU CLispGCL),以Homebrew安裝的2.49版為主。以下是如之前效果的程式碼,看起來不太像Lisp,我寫得太不優雅了,只能盡可能寫的清楚。

(defun addlist(newList)
 (setq result (append result (list (reverse newlist))))
)

(defun calc(before all want)
 (cond 
  ((= want 0)
   (setq rest (loop for i from 1 to all append (list 0)))
   (addlist (append before rest)))
  ((= all want) 
   (setq left (- all want)) 
   (setq rest (loop for x from 1 to all append  (list 1)))
   (addlist (append before rest)))
  ((= all 1)
   (addlist (append before (list want))))
  (t 
   (calc (append before (list 0)) (- all 1) want)
   (calc (append before (list 1)) (- all 1) (- want 1)))
 )
)

(defun combinations (all want)
 (setq result (list))
 (setq lst (list) )
    (calc lst all want)
)

(combinations 3 2)
(print result)

以下是正常版組合的Lisp程式碼:
(defun addlist(newList)
 (setq result (append result (list (reverse newlist))))
)


(defun combinations (all want )
 (setq result (list))
 (setq lst (loop for x from 1 to all append  (list x))) 
    (labels ((calc (l c want)
     (when (>= (length l) want)
        (if (zerop want) (return-from calc (addlist c)))
         (calc (cdr l) c want)
         (calc (cdr l) (cons (first l) c) (1- want)))))
         (calc lst nil want))
 (setq result (reverse result))         
)

(combinations 3 2)
(print result)

沒有留言: