Re: [clisp-list] A few beginner problems

[Klaus E. G. <gr...@di...>]

;; Hi,
;; Im a LISP beginner and I would like some help.
;; I have 2 problems that might be easy for an advanced programmer:

; I wonder whether or not cli...@li... is the right
; place to ask such questions. But I had a little spare time this morning,
; so here is a partial answer to question 2 and 3 in case you want to
; write your program in a do-it-yourself-style (which I think is a good
; idea until you are no longer a LISP beginner).

(in-package "COMMON-LISP-USER")



;; 2. A function that returns a list containing integers between sets of 
;; lower and upper boundaries. For example: function 20 26 23 28 would 
;; return: (20 21 22 23 24 25 26 27 28)

; (integer-interval m n) returns the list (m m+1 m+2 ... n) provided
; that m and n are integers and m <= n.

(defun integer-interval (m n)
  (if (< n m) nil
   (cons m (integer-interval (+ m 1) n))))

; (integer-interval-1 m n) also returns the list (m m+1 m+2 ... n)
; provided that m and n are integers and m <= n. But it runs faster.

(defun integer-interval-1 (m n)
  (integer-interval-2 m n nil))

; (integer-interval-2 m n result) returns the list (m m+1 m+2 ... n)
; prepended to the list 'result'.

(defun integer-interval-2 (m n result)
  (if (< n m) result
   (integer-interval-2 m (- n 1) (cons n result))))

; The function above is 'tail recursive' in the sense that the very
; last thing it does when (< n m) is false is that it calls *itself*.
; The integer-interval function is not tail recursive: the last thing
; it does when (< n m) is false is that it calls 'cons'. Tail recursive
; functions happen to be faster than other functions on most systems.

; (question-2 s) returns a list with all integers between the smallest and
; largest element of the non-empty list s of integers. As an example,
; (question-2 '(20 26 23 28)) returns (20 21 22 23 24 25 26 27 28)

(defun question-2 (s)
  (integer-interval-1 (apply 'min s) (apply 'max s)))

; The function above uses (apply 'min s) to apply the minimum function to
; the list s to get the smallest element of the list. If you want to do
; that 'yourself' you can use (smallest-element s) instead:

(defun smallest-element (s)
  (if (atom (cdr s)) (car s)
   (min (car s) (smallest-element (cdr s)))))

; The smallest-element function above is *not* tail recursive. One can make
; it tail recursive and thereby faster using the same trick as the one I
; used for integer-interval above.



;; 3. A random generator that chooses values form a list or a stackpile 
;; without repeating any values until all have been used once.

; The following is *not* a solution to your problem. Rather, I solve
; the related problem of constructing a random permutation of the
; integers from m inclusive to n exclusive. Hopefully, you can adapt
; the code to suit your needs

; (random-permutation m n) returns a random permutation of the numbers
; m,m+1,m+2,...,n-1 provided that m and n are integers and m < n.

(defun random-permutation (m n)
  (format t "random-permutation ~s ~s~%" m n)
  (if (= m (- n 1)) (list m) (random-permutation-1 m (floor (+ m n) 2) n)))

; (random-permutation-1 m d n) returns a random permutation of the numbers
; m,m+1,m+2,...,n-1 provided that m, n, and d are integers and m < d < n.

(defun random-permutation-1 (m d n)
  (format t "random-permutation ~s ~s ~s~%" m d n)
  (random-merge
   (- d m) (random-permutation m d)
   (- n d) (random-permutation d n)))

; (random-merge l1 s1 l2 s2) returns a random merge of the lists s1 and s2
; provided that l1 is the length of s1 and l2 is the length of s2. When
; merging a short and a long list it picks with largest probability from
; the long list. To get all permutations with even probability it is
; important to pick with probability l1/(l1+l2) from the list of length l1.

(defun random-merge (l1 s1 l2 s2)
  (format t "random-merge ~s ~s~%" l1 l2)
  (if (= l1 0) s2
   (if (= l2 0) s1
    (if (< (random (+ l1 l2)) l1)
     (cons (car s1) (random-merge (- l1 1) (cdr s1) l2 s2))
     (cons (car s2) (random-merge (- l2 1) (cdr s2) l1 s1))))))

; Cheers,
; Klaus