The Classical Josephus Problem

This is another one taken from Programming Praxis #5 – Flavius Josephus, has a historical context which can be found here. For this exercise, write a function j that takes two values n & m that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed, every mth person in turn, with the sole survivor as the last person in the list. What is the value of j (41,3)? In what position did Josephus survive?

Built a recursive routine that executes each soldier and creates a smaller and smaller live soldier list. Used Debug.Trace to list each one executed, rather than build an execution list.

import Debug.Trace

execute :: [Int] -> Int -> Int -> [Int]
execute [a] _ _ = [a]
execute soldiers inc pos = trace (show v) $ execute [x | x <- soldiers, x /= soldiers !! pos] inc newPos
	where
		newPos
			| (pos + inc) >= length soldiers = pos + inc - length soldiers
			| otherwise = pos + inc - 1
		v = (soldiers, inc, pos, newPos)

main = print $ j 41 3
	where
		j numSoldiers inc = execute [1..numSoldiers] inc $ inc - 1