플라비우스 요세푸스 순열

요세푸스 순열은
유대인 역사가 플라비우스 요세푸스의 이야기에서 유래한 수학적 문제이다.

요세푸스의 이야기

1세기 로마 제국 시대, 유대인은 로마에 대항하여 대규모 반란을 일으켰다.
이 때, 요세푸스는 유대 반군의 장군 중 한명으로 로마군에 의해 포위당했다.
전투에서 패배한 요세푸스와 동료들은 로마군에 항복하는 대신 자결하는 것을 택했다.
하지만 자결하는 것은 두려웠는지 원형으로 앉았고, 특정 규칙에 따라 순차적으로 서로 죽여주는 방식을 택했다.

1. 특정 수의 인원을 건너 뛰고 다음 사람을 제거한다.
2. 마지막 한 사람이 남을 때까지 반복.

그러나 요세푸스는 동료들의 뜻에 반대하여 살고 싶었고, 위 규칙을 이용하여 마지막 한 사람이 되어 로마군에 항복하였다.

 

공식

일반적인 공식은 다음과 같다. 

n : 인원 수

k : 건너뛸 수

재귀함수 형식을 띄고 있다.

 

 

예시)

f( 7, 3 ) 인 경우

idx	f( N, K )	( N + K ) mod N	result
1	(7, 3)	(0 + 3) % 7	3
2	(6, 3)	(3 + 3) % 6	0
3	(5, 3)	(0 + 3) % 5	3
4	(4, 3)	(1 + 3) % 4	0
5	(3, 3)	(1 + 3) % 3	1
6	(2, 3)	(0 + 3)  % 2	1
7	(1, 3)	N = 1	0

 

코드

재귀 코드로 구현하면 다음과 같이 구현할 수 있다.

package org.example;

public class Main {
    public static int josephus(int N, int K) {
        if (N == 1) return 0;
        return (josephus(N - 1, K) + K) % N; // 재귀 호출
    }

    public static void main(String[] args) {
        int N = 7;
        int K = 3;
        System.out.println("Last survivor: " + (josephus(N, K) + 1));
    }
}

 

결과 ( 마지막 생존 자리 )

4

 

이번에는 재귀함수로 해결하였지만, 원형 큐 등 다양한 방법들이 있다.
생존을 위해서 역사가의 새로운 순열 공식
순차적인 제거 문제에서 다양하게 사용되고 있다.