SHARE
TWEET

Programming Praxis: Flavius Josephus

yuridichesky Feb 17th, 2012 171 Never
  1. ;; Programming Praxis
  2. ;; http://programmingpraxis.com/2009/02/19/flavius-josephus
  3. ;; Flavius Josephus
  4. ;; Written in Scheme (Guile 2.0)
  5. ;; (josephus 41 3) ->
  6. ;;   (2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25
  7. ;;   33 39 7 16 28 37 10 24 1 21 3 34 15 30)
  8.  
  9. (define (josephus n m)
  10.   (let loop ((s (apply circular-list (iota n)))
  11.              (n n)
  12.              (res '()))
  13.     (if (= 1 n) (reverse (cons (car s) res))
  14.       (let* ((x (drop s (- m 2)))   ;; element preceding the element to remove
  15.              (y (cadr x)))          ;; element to remove
  16.         (set-cdr! x (cddr x))   ;; remove element from circular list
  17.         (loop (cdr x) (1- n) (cons y res))))))
RAW Paste Data
Top