Want more features on Pastebin? Sign Up, it's FREE!
Guest

Programming Praxis: Flavius Josephus

By: yuridichesky on Feb 17th, 2012  |  syntax: Scheme  |  size: 0.69 KB  |  views: 135  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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))))))
clone this paste RAW Paste Data