Josephus Permutation

September 13th 2018

Josephus Permutation

This problem takes its name by arguably the most important event in the life of the ancient historian Josephus: according to his tale, he and his 40 soldiers were trapped in a cave by the Romans during a siege.

Refusing to surrender to the enemy, they instead opted for mass suicide, with a twist: they formed a circle and proceeded to kill one man every three, until one last man was left (and that it was supposed to kill himself to end the act).

Well, Josephus and another man were the last two and, as we now know every detail of the story, you may have correctly guessed that they didn't exactly follow through the original idea.

You are now to create a function that returns a Josephus permutation, taking as parameters the initial array/list of items to be permuted as if they were in a circle and counted out every k places until none remained.

Tips and notes: it helps to start counting from 1 up to n, instead of the usual range 0..n-1; k will always be >=1.

For example, with n=7 and k=3 josephus(7,3) should act this way.

[1,2,3,4,5,6,7] - initial sequence
[1,2,4,5,6,7] => 3 is counted out and goes into the result [3]
[1,2,4,5,7] => 6 is counted out and goes into the result [3,6]
[1,4,5,7] => 2 is counted out and goes into the result [3,6,2]
[1,4,5] => 7 is counted out and goes into the result [3,6,2,7]
[1,4] => 5 is counted out and goes into the result [3,6,2,7,5]
[4] => 1 is counted out and goes into the result [3,6,2,7,5,1]
[] => 4 is counted out and goes into the result [3,6,2,7,5,1,4]

// So our final result is :
josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4]

고대 역사학자 조세프스와 그의 병사는 로마군에 포위되어 동굴에 갇혔습니다. 항복하는 대신 그들은 원으로 둘러선 후, 돌아가며 세 번째에 선 사람을 죽이고 마지막 남은 사람은 자결하기로 했습니다. 조세프스와 다른 한 명의 병사만 남았을 때 그들은 마음을 바꿔 로마군에 항복했습니다.

위 이야기를 참고해 배열과 수를 전달받으면, 전달받은 수의 간격으로 순차적으로 배열의 요소를 취해 새로운 배열을 반환하는 문제입니다. 저의 문제 해결 과정을 풀이해 보면,

- 처음 전달받은 배열의 길이가 0이 될때까지 각 요소를 반복하며 돕니다. - loop의 횟수와 k의 수가 같아지면, k위치에 있는 배열의 요소를 취해 새로운 배열에 추가합니다. - 초기 배열의 길이가 0이 될 때까지 위 작업을 반복한 후, 새로운 배열을 반환합니다.

function josephus(items, k) {
  var index = 0;
  var count = 1;
  var dead = [];

  while (items.length > 0) {
    if (count === k) {
      dead.push(items.splice(index, 1)[0]);
      count = 0;
      index--;
    }

    index++;
    count++;

    if (index === items.length) {
      index = 0;
    }
  }

  return dead;
}

아래는 추천수가 많은 코드를 가져왔습니다. 제 코드가 오징어가 되는 느낌이군요...; 요소를 취할 인덱스를 찾고 새로운 배열에 추가하는데 modulo operator를 이용해 한 줄로 작성했네요.

function josephus(items, k) {
  var dest = [],
    i = 0;

  while (items.length > 0) {
    dest.push(items.splice((i = (i + k - 1) % items.length), 1)[0]);
  }

  return dest;
}

아래 코드는 위의 코드와 내용은 동일하나, 결과 값 배열을 concat method를 이용해 완성했습니다.

function josephus(items, k) {
  var result = [],
    index = 0;

  while (items.length > 0) {
    index = (index + k - 1) % items.length;
    result = resutl.concat(items.splice(index, 1));
  }

  return result;
}

Handmade with .