Josephus in Scheme

Question

Where does this implementation of the Josephus problem fall short? For those who are unfamiliar with the Josephus Problem, the goal is to delete every 3rd entry from a circularly linked list until only one remains. In this example I am deleting every "mth" value.

(define (joseph lst)  
(let ((m (+ 1 (random (length lst)))))
(define (joseph-h i xlst mlst)
 (cond ((<= (length xlst) 1) xlst)
       ((null? (cdr mlst)) 
        (joseph-h i xlst xlst))
       ((= i m) 
        (joseph-h 1 (delete (car mlst) xlst) (cdr mlst)))
       (else 
        (joseph-h (+ i 1) xlst (cdr mlst)))))
 (joseph-h 0 lst lst)))

 (joseph (list 1 2 3 4 5 6 7))


 (define (delete v lst)
   (cond ((= v (car lst)) 
          (cdr lst))
         (else
          (cons (car lst) (delete v (cdr lst)))))) 

I always end up with the last number of the list as the answer. I know that this is not right.

Answer 1

You're taking the algorithm too literally, by creating a list and deleting elements ("killing" people) from it. A simpler solution would be to use arithmetic operations to model the problem, here's a possible implementation, adapted from my own previous answer:

(define (joseph n k)
  (let loop ([i   1]
             [acc 0])
    (if (> i n)
        (add1 acc)
        (loop (add1 i)
              (modulo (+ acc k) i)))))

For example, to see which position survives in the list '(1 2 3 4 5 6 7) after killing every third person, do this:

(joseph 7 3)
=> 4

Wikipedia provides an interesting discussion regarding the possible solutions for this problem, my solution adapts the simple python function shown, after converting it to tail recursion.