Description: There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.
I Googled this ‘Josephus problem’ and the Wikipedia hit gives me a dynamic-programming solution: f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, but this only yields the last survivor. How can I get the sequence of the people executed? Say, p(5, 3) = {3,1,5,2,4}.
Also, is there a O(nlogn) solution instead of a O(nk) one?
Advertisement
Answer
To get sequence of executed persons and last survivor you just need to simulate whole process from the beginning. Given description of procedure this would be quite easy task. Formula that you present is only shortcut to check who will survive and to obtain answer quickly.
Description on how to do this in O(n log n) using Range Trees is here: http://pl.scribd.com/doc/3567390/Rank-Trees
More detailed analysis can be found here: http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf