Notes and comments on assignment 1, with some solutions

4. (LengthAtLeast...)

There are a wide variety of answers here. Although declarations can
help in making programs run fast, we especially wanted you to check so
that a very long list (much longer than n) would not cause a long
computation.  Checking for a proper list is another concern -- in fact
the function  length used above checks for ``non-proper'' lists
like '(A B . C). Here's an improvement:


(defun LengthAtLeast(x n)

  "return T if x is a proper list of length n or more else return NIL."

  (assert (listp x) (x)) ;;this does not check completely for proper list.
  (assert  (integerp n) (n)) ;; n must be a number if we do arithmetic on it.

  ;; it checked out so far, so call the recursive part
  (lal x n))

(defun lal (x n) ;could be a local function
 (cond ((<= n 0) t)
       ((null x) nil)
       ((listp x) (lal (rest x) (1- n)))))

;;;ANOTHER WAY -- IGNORE ALL ERRORS

(defun LengthAtLeast2(x n)
 (handler-case (lal x n)
   (error () nil))) ;; any error --> nil


Using various do constructs is acceptable, but considerations of
efficiency may actually favor this program.  The function lal is
properly tail recursive and should compile into something quite
efficient in most modern lisp systems.


5. Why is this program ugly? 

This program fails to provide a mnemonic name or any documentation.
The use of do is somewhat disconcerting for novice readers since the
``body'' is empty. (Although this kind of construction is correct and
not that unusual in practice.)  Its use of the back-quote macro is
obscure, unnecessary, and quite inefficient. The expression `(,@ans
,i) is equivalent to (append ans (list i)).  Instead of appending
singleton lists of numbers to the back of a list, re-copying the list
each time, the function nconc could be used instead of append.  This
would still be wasteful since the numbers could be consed to the
front, by (cons i ans) but then the numbers are in reverse order.  It
is then possible to nreverse the list. Even this is unnecessary work:
just generate the  i numbers in reverse order.  In improving this
code we have replaced an $O(n^2)$ algorithm with an $O(n)$. (If
you don't see why, ask.)

Overall, the simplest way of writing it may be:


(defun ListOfNumbers(n)
" construct a list of the numbers from 1 to the integer n"
 (check-type n integer)
 (loop for i from 1 to n collect i))

6.   (checking for permutations)

Here  are a collection of 6 answers.  The first is probably not linear time
because  set-difference is (I suspect) not linear time. The others
are linear time. Among the linear-time ones,  perm2 seems 
fastest on a list of 500 elements.

(defun perm1(x)                     ;probably not linear time

"Return T if x is a list of the integers from 1 to (length x), permuted.
   Gives an error if x is not a proper list."

  (null (set-difference (ListOfNumbers (length x)) x)))


(defun perm2 (x)                   ;linear time

  "Return T if x is a list or vector of the integers from 1 to
  (length x), permuted.  Gives an error if x is not a sequence"

;;  If there are L numbers e[1], e[2],... e[L],  and each
;;  number can be put in one of the boxes labelled with its value
;;  1, 2, ... L, with no duplicates, then {e[i]} must be a permutation
;;  of the integers from 1 to L. (Pigeon-Hole principle)

   (let* ((len (length x))
          (ar (make-array (1+ len) :element-type 'bit :initial-element 0)))
     (every
      #'(lambda(e)(and(integerp e)
                      (<= 1 e len)
                      (zerop (aref ar e))
                      (incf (aref ar e))))
      x)))


;; perm3 below has the interesting property of not needing any intermediate
;; storage for lists of length shorter than (log most-positive-fixnum 2).
;; It is also more interesting to prove it correct.  Sketch: if x has n
;; 1 bits in its binary representation, then x + 2^i will have n+1 1 bits
;; if x had a 0 at position i, and will have at most n 1 bits otherwise.
;; So if the list were not a permutation, we couldn't get all the bits set.
 

(defun perm3 (list)
  (= (loop for e in list sum (expt 2 (- e 1)))
     (- (expt 2 (length list)) 1)))

;; and just to show that you can always hack a hack, here 
;; are 2 more

(defun perm4 (list)  ;;less testing, less arithmetic in loop
  (= (loop for e in list sum (ash 1 e)) (- (ash 2 (length list)) 2)))

(defun perm5(list &aux (len (length list))) ;;more testing
  (= (loop 
         for e in list 
         do (unless (and (integerp e) (<= 1 e len))
              (return-from perm5 nil))
         sum (ash 1 e ))
     (- (ash 2 len) 2)))



(defun perm6(list) ; suggested in 1999
  (let ((n (length list)))

(and (= (apply #'* list) (fact n))
     (= (apply #'+ list) (* n (1+ n) 1/2)))))
;;where
(defun fact(n)(if (= n 0)1(* n (fact (1- n)))))




...............
more notes

(defun lon2(n)(if (= n 0)nil(cons n (lon2 (1- n)))))
(defun lon3(n)(lon3a n nil))(defun lon3a (k L)(if (= k 0)L(lon3a (1- k) (cons k L))))
 or..
 (defun lon3a (k L)(declare (optimize (speed 3)(safety 0))(fixnum k))
  (if (= k 0)L(lon3a (1- k) (cons k L))))