;
;circle.lisp
;
;algorithm to repeatedly remove k'th item
;from circular list and determine which
;element is last to remain.
;algorithm is o(n) given input n, size of list
;note that algorithm is independent of k because
;(mod k n) is always used to determine which element
;of list to remove
(defun circle-nth(l k)
"Compute index, from 0 to length of list, of k-th item in list l.
Uses the trick that for any k, (mod k (length l))
is the correct index which is equivalent to walking through the list
circularly to get the k-th item -- saves steps for k > (length l)... "
(mod k (length l))
)
(defun circle-remove(l n)
"Remove (circle-nth n)-th item in list l"
(let
(
(k-th (circle-nth l n))
)
(format t "Remove #~d from ~s~%" k-th l)
(cond
((null l) nil) ; can't remove from empty list
((zerop k-th) (butlast l)) ; index 0 means remove last element
(t
(append ; construct returned list from
(nthcdr k-th l) ; succeeding cdr and
(firstn (sub1 k-th) l) ; list preceding removed element
)
)
)
)
)
(defun circle-last(l k-th)
"Remove k-th item in list l until only 1 element left"
(format t "~%")
(if
(cdr l)
(circle-last (circle-remove l k-th) k-th) ; recurse 'til only one element left
(car l)
)
)
(defun circle-demo(n k)
"Demonstrate circular removal algorithm for a given n, k"
(cond
((null (integerp n)) (format t "~%N must be an integer!~%"))
((null (integerp k)) (format t "~%K must be an integer!~%"))
((lessp n 1) (format t "~%N must be >= 1!~%"))
((lessp k 1) (format t "~%K must be >= 1!~%"))
((greaterp n 26) (format t "~%N must be <= 26!~%"))
(t
(prog (demlist last-one)
(setq demlist '(a b c d e f g h i j k l m n o p q r s t u v w x y z))
(setq demlist (firstn n demlist))
(format t "~%Remove every ~d~a" k
(case k
(1 "st")
(2 "nd")
(3 "rd")
(t "th")
)
)
(format t " element from ~s~%" demlist)
(setq last-one (circle-last demlist k))
(format t "~%Only ~a remains.~%" last-one)
(return last-one)
)
)
)
)