#-(and) "
   
P23 (**) Extract a given number of randomly selected elements from a list.
    The selected items shall be returned in a list.
    Example:
    * (rnd-select '(a b c d e f g h) 3)
    (E D A)
   
    Hint: Use the built-in random number generator and the result of problem P20.
"

;; The word "extract" and P20, seem to hint that a given element may
;; be choosen only once.  Must the order be random too?




;; Recursive solution using the function remove-at of P20:

(defun rnd-select (list count)
  (if (zerop count)
      '()
      (let ((i (random (length list)))) ; lenght and elt are O(n) ==> rnd-select is O(n²).
        (cons (elt list i) (rnd-select (remove-at list (1+ i)) (1- count))))))


;; Iterative solution using the function remove-at of P20:

(defun rnd-select (list count)
  (loop
     :repeat count
     :for len :from (length list) :by -1
     :for i = (random len)
     :collect (elt list i) ; elt is O(n) ==> rnd-select is O(n²).
     :do (setf list (remove-at list (1+ i)))))


;; This solution extract the items in the same order than in list, by
;; precomputing a random bitmap.  The result is O(n):

(defun rnd-select (list count)
  (let ((len (length list)))
    (cond
      ((zerop count) '())  ; none selected.
      ((= count len) list) ; all selected.
      ((< 0 count len)
       (let ((bits (make-array len :element-type 'bit :initial-element 0)))
         (loop
            :while (plusp count)
            :for i = (random len)
            :do (when (zerop (aref bits i))
                  (setf (aref bits i) 1)
                  (decf count)))
         (loop
            :for item :in list
            :for indicator :across bits
            :when (plusp indicator)
            :collect item)))
      (t (error "Invalid count, must be between 0 and ~A" len)))))


;; This other solution remembers the indices selected, and avoids
;; reusing them.  This gives a random order, but the time complexity
;; is not deterministically bound, only statistically bound (assuming
;; a correct pseudo-random  generator):

(defun rnd-select (list count)
  (let ((len (length list)))
    (cond
      ((zerop count) '())  ; none selected.
      ((<= 1 count len)
       (loop
          :with indices = '()
          :with result  = '()
          :while (plusp count)
          :for i = (random len)
          :unless (member i indices)
          :do (progn
                (push i indices)
                (push (elt list i) result) ; elt is O(n) ==> rnd-select is O(n²).
                (decf count))
          :finally (return result)))
      (t (error "Invalid count, must be between 0 and ~A" len)))))


;; Other algorithms for random arrangements can be found in TAOCP...

;;;; THE END ;;;;