combinations

[vimsical]

Giving myself some exercise to learn lisp, I am writing a function display all binary strings of length N with s 1's. And I got this:

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)))

Right now this code strike me as very non-LISP-ish. Among other things, is the

Code: Select all

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

a good way to return a value? Any instructive comment would be very welcomed.

--
MLfZ

[ramarren]

Your 'as' function already exists in Common Lisp, see MAKE-LIST. Also your function has square complexity, since you unnecessarily traverse the list as it is constructed. In Lisp it is usually better to construct a list by attaching elements from the front using CONS and then NREVERSE if necessary.

You don't need to quote NIL. NIL is a self evaluating constant. Numbers are also self-evaluating.

A returned value should usually be a result of an expression. The way you ask about is sometimes appropriate, but rarely. Especially when recursive functions are involved. You want to be the function to be defined in terms of itself, which is unclear when side effects start getting involved. And as I said, constructing a list from the front is better, especially when order doesn't matter like in this case. I would write it this way (correctness not guaranteed):

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))))))

[vimsical]

Thanks. This is exactly what I am talking about. Usually with good LISP code, I can just read off the algorithm, instead of my spaghetti. I am a few chapter into "ANSI Common LISP" and so doesn't know all the available tools. In fact, I first tried to use (cons ... ) but got confused few times when I end up with list like ((0 0 0) 0 1 0), when I meant to get ((0 0 0) (0 1 0)). More study obviously.