Random Sublists.

; This is old trick but some might be interested. The problem is:
; define function that returns random, n element sublist of a given
; list.

; There are many ways it can be done in Newlisp, and here is one
; that requires O(length(L)) time, no matter of n. That is pretty
; good, and if lists are implemented as linked lists, better order
; of value is not possible.
;
; Algorithm pass through whole list once and inspect all elements,
; from first to last. Lets say L=(2 6 7 9 4) and we want to find
; random three element sublist.

; First we'll consider 2 as a candidate for our sublist. The
; probability that it will be included in list should be 3/5=0.6.

; We chose random number between 0 and 1 and if it is less than
; 0.6, number 2 will be inserted in sublist. Then we proceed to
; chose two elements from (6 7 9 4).
;
; If random number between 0 and 1 is greater than 0.8, we do
; not include it in sublist, and then we proceed to chose three
; elements from (6 7 9 4).


(set 'random-sublist
    (lambda(L pick-from-list)
      
      (let ((result '())
            (left-in-list (length L)))
            
           (when (> pick-from-list left-in-list)
            (throw-error (append "There is no n=" (string pick-from-list)
                                 " elements in L.")))
                                 
           (dolist (element L (= pick-from-list 0))
                   (let ((probability (div pick-from-list
                                           left-in-list)))
                   
                         (when (<= (random 0 1) probability)
                               (push element result -1)
                               (dec pick-from-list))
                         (dec left-in-list)))

            result)))




(seed (date-value))
(for (j 0 5)
  (for (i 1 15)
     (print (random-sublist '(1 2 3 4 5) j)))
     (println))

; Here is what happens if one tries to chose larger sublist than
; list:

(random-sublist '(2 3 4 5 6) 8)

; Result:


()()()()()()()()()()()()()()()
(1)(3)(4)(2)(3)(5)(2)(4)(3)(3)(5)(3)(4)(3)(2)
(1 3)(1 2)(2 3)(3 4)(2 5)(3 4)(4 5)(4 5)(1 2)(3 5)(1 2)(1 2)(1 2)(2 3)(4 5)
(3 4 5)(1 3 4)(1 2 4)(1 3 5)(2 3 5)(2 3 4)(2 4 5)(2 3 4)(1 3 4)(1 2 3)(1 3 4)(1 2 4)(1 3 5)(3 4 5)(1 2 3)
(2 3 4 5)(1 3 4 5)(1 2 3 4)(1 2 4 5)(1 2 3 4)(1 2 4 5)(1 2 3 5)(1 3 4 5)(1 2 4 5)(1 2 3 5)(2 3 4 5)(1 2 3 5)(1 2 3 4)(1 2 3 4)(1 2 4 5)
(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)(1 2 3 4 5)

ERR: user error : There is no n=8 elements in L.
called from user defined function random-sublist