JavaScriptでJosephus順列を効率的に計算する

この問題は、古代の歴史家ヨセフスの人生でおそらく最も重要な出来事にちなんで名付けられました。彼の話によると、彼と彼の40人の兵士は、ローマ人によって洞窟に閉じ込められました。包囲。

彼らは敵に降伏することを拒否し、代わりにひねりを加えて集団自殺を選択しました-彼らは輪を作り、最後の一人が残るまで（そして行為を終わらせるために自分自身を殺すはずだった）、3人に1人の男を殺し始めました。

ヨセフスともう一人の男が最後の2人でした。物語の詳細がすべてわかったので、彼らが元のアイデアに正確に従わなかったと正しく推測したかもしれません。

ヨセフスの順列を返すJavaScript関数を作成する必要があります。

パラメータとして、最初の配列/アイテムのリストを、それらが円の中にあるかのように並べ替え、残りがなくなるまでkか所ごとにカウントします。

たとえば、n=7およびk=3の場合、josephus（7,3）はこのように動作する必要があります。

[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]

したがって、最終結果は-

josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4];

例

このためのコードは-

const arr = [1, 2, 3, 4, 5, 6, 7];
const num = 3;
const helper = (n, k, i, map) => {
   if (map.hasOwnProperty([n, k, i]))
   return map[[n, k, i]];
   if (i === 1)
   return map[[n, k, i]] = (k − 1) % n;
   return map[[n, k, i]] =
   (k + helper(n − 1, k, i − 1, map)) % n;
}
const josephus = (arr, k) => {
   let n = arr.length;
   let result = new Array(n);
   let map = {};
   for (let i=1; i<=n; i++)
   result[i − 1] = arr[ helper(n, k, i, map) ];
   return result;
};
console.log(josephus(arr, num));

出力

そして、コンソールの出力は-

[
   3, 6, 2, 7,
   5, 1, 4
]