Josephus sequence

问题:

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?

回答1:

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

回答2:

The most natural data structure to represent the people is a circular buffer. My solution creates a linked list, ties the tail of the list back to the head, then repeatedly counts around the buffer to the next person to be executed, removes that person from the buffer, and continues until the tail of the buffer points to itself.

(define (cycle xs)
  (set-cdr! (last-pair xs) xs) xs)

(define (josephus n m)
  (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '()))
    (cond ((= (car alive) (cadr alive))
            (reverse (cons (car alive) dead)))
          ((= k 1)
            (let ((dead (cons (cadr alive) dead)))
              (set-cdr! alive (cddr alive))
              (loop (- m 1) (cdr alive) dead)))

For example:

> (josephus 41 3)
(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 33 39 7 16 28 37 10 24 1 21 3 34 15 30)

You can read a fuller explanation at my blog, which gives three different solutions. Or you can run the program at http://programmingpraxis.codepad.org/RMwrace2.

回答3:

The people would be stored in array of size n. If the person at index i was executed now, the next would be given by (i+k)%m where m is the number of people remaining. After every iteration, the array size would decrease by 1 and the remaining elements will be accordingly shifted.

Input: People[0..n-1], n, k, i (= index of first person executed)

The pseudo code would be something like:

Print People[i]

While (n > 1)
do
  n = n - 1
  for j = i to n-1
    People[j] = People[j+1]
  i = (i+k) % n
  print People[i]
done

回答4:

To stimulate the program you can use a struct which contain the name of the player and a tag which keep the track if the player is active or not. Every time in a new round you skip a particular number of players, so use a loop and and a conditional statement so that all the players which are out of the game are ignored and only those in the game are counted. And of course add printf statements to print the current status.

回答5:

To answer this question of outputting the sequence of execution, a simulation is required. This means O(nk) complexity. It is impossible to get sequence of execution [which is O(n)] while seeking O(nlogn) time complexity at the same time. Because you must output every person to be executed, which is O(n).

kkonrad's reference to Range Trees yield a nice O(nlogn) solution. As others have pointed out, a circular linked list is an efficient data structure for this problem. I find 200_success' Java solution from Code Review to be very elegant and readable.

public class CircularGunmenIterator<T> implements Iterator<T> {

  private List<T> list;
  private Iterator<T> iter;

  public CircularGunmenIterator(List<T> list) {
    this.list = list;
    this.iter = list.iterator();
  }

  @Override
  public boolean hasNext() {
    // Continue as long as there is a shooter and a victim
    return this.list.size() >= 2;
  }

  @Override
  public T next() {
    if (!this.iter.hasNext()) {
      // Wrap around, creating the illusion of a circular buffer
      this.iter = this.list.iterator();
    }
    return this.iter.next();
  }

  @Override
  public void remove() {
    this.iter.remove();
  }

  public static void main(String[] args) {
    // Create the gunmen
    List<Integer> gunmen = new LinkedList<Integer>();
    for (int i = 1; i <= 100; i++) {
      gunmen.add(i);
    }

    // Shootout!
    Iterator<Integer> ringIter = new CircularGunmenIterator<Integer>(gunmen);
    while (ringIter.hasNext()) {
        Integer shooter = ringIter.next();
        Integer victim  = ringIter.next();
        System.out.printf("%2d shoots %2d\n", shooter, victim);
        ringIter.remove();  // Bang!
    }
    System.out.println("Last one alive: " + gunmen.get(0));
  }
}

There are some more details on Wikipedia for this Josephus problem (k = 2).

http://en.wikipedia.org/wiki/Josephus_problem