LispForum

Code: Select all

;; as(a N) return list (a a ... a) consists of N a's
(defun as (a N)
  (if (= N 0) 'nil
    (append (as a (- N 1)) (list a))))

;; Generate binary strings of N chars with s 1's.
(defun combination (N s)
  (if (= s 0)                     ;; If s = 0, just return N 0's
    (list (as '0 N))
    ;; (s > 0):
    (let ((d 'nil))
      (loop
        for j from (- s 1) below N do ;; loop through possible locations of last "1"
        (progn
          (dolist (k (combination j (- s 1))) ;; for each binary strings of j chars with (s-1) "1"
          (setf d                             ;; append to list k .. 1 0 .. 0
                (append d
                          (list (append k
                                        (list '1)
                                        (as '0 (- (- N j) 1)))))))
          ))
      d)))

Code: Select all

(let ((d init)) ( ... d))

Code: Select all

(defun combination (n s)
  (cond ((zerop n) nil)
        ((zerop s) (list (make-list n :initial-element 0)))
        ((= n s) (list (make-list n :initial-element 1)))
        (t (append (mapcar #'(lambda (l)
                               (cons 1 l))
                           (combination (1- n) (1- s)))
                   (mapcar #'(lambda (l)
                               (cons 0 l))
                           (combination (1- n) s))))))