요세프스 순열(Josephus Permutation)

요세프스 순열의 기원은 요세프스라는 인물이 유대-로마 전쟁시에 살아 남은 일화를 바탕으로 하는데 그 일화를 위키피디아에서 가져와봤다.

제1차 유대-로마 전쟁에서 예루살렘에서 갈릴리로 파견되어 갈릴리의 마을인 요타파타를 지키는 지휘관으로서 로마군에 맞섰으나, 로마군 사령관 베스파시아누스 플라비우스·티투스 부자가 지휘하는 로마군에게 패하고 만다. 이때 이방인에 대한 투항보다 차라리 자결하는 쪽을 택한 다른 유대인 지휘관들은 제비를 뽑아 서로 죽였지만, 마지막으로 요세푸스와 다른 병사 한 명이 남겨졌을 때 요세푸스는 그 병사를 설득해 함께 로마군에 투항하였다. 기원후 67년 7월의 일이었다.

<위키피디아: 플라비우스_요세푸스 중 일부>

이때 순서를 정하는 방식을 요세푸스 순열이라고 하는데, n명이 동그랗게 서서 임의의 한 명부터 k번째 사람을 제외하고, 다시 n-1명에서 k번째 사람을 제외하여 모두 제외될 때까지 반복하는 방식이다. 예를 들어 {1, 2, 3, 4, 5, 6, 7} 7명이 있고 3번째 마다 제외 하기로 한다면, 아래와 같이 {3, 6, 2, 7, 5, 1, 4} 라는 결과를 얻을 수 있다. (n=7, k=3)

{1, 2, 4, 5, 6, 7} => {3}
{1, 2, 4, 5, 7} => {3, 6}
{1, 4, 5, 7} => {3, 6, 2}
{1, 4, 5} => {3, 6, 2, 7}
{1, 4} => {3, 6, 2, 7, 5}
{4} => {3, 6, 2, 7, 5, 1}
{} => {3, 6, 2, 7, 5, 1, 4}

이걸 C++ 함수로 구현해 보았다. nums 에서 k번째 수를 하나씩 제거해서 res에 넣고 모두 제거하면 res를 리턴하는 방식이다.

// 
// nums: {1,2,3,4,5,6,7}
// k: 3
// res: {3,6,2,7,5,1,4}
std::vector<int> GetJosephusPermutation(std::vector<int> nums, int k) { 
  
    std::vector<int> res;
    int curInd = 0;
    while(1)
    {
         if( nums.empty() ) break;
      
         int ind = (curInd + k - 1) % nums.size();

         res.push_back(nums[ind]); 
         nums.erase(nums.begin() + ind); 
         curInd = ind;
    }

    return res;
}

요세푸스가 이 방식으로 살아남은 것에 대한 해석은 다양한 것으로 보인다. 나라를 팔아먹었다, 혹은 강한 것에 굴복하는 것은 당연하다 등등. 어쨌든 마지막 두명 남았을 때 다음 순서가 요세푸스였던 것은 분명하다. 그게 아니었으면 자신이 혼자 남을 때까지 진행하지 않았을까.

Featured Image from https://en.wikipedia.org/wiki/File:JosephusProblemDrawing.png

---