JavaScriptでヨセフス順列を効率的に計算する方法

ヨセフス問題とは

「ヨセフス問題」の名前は、古代ユダヤの歴史家フラウィウス・ヨセフスの人生における最も重要な出来事に由来しています。彼自身の記述によれば、包囲戦の際にヨセフスと40人の兵士はローマ軍によって洞窟に追い詰められたとのことです。

敵に降伏することを潔しとしなかった彼らは集団自決を選びましたが、そこに独自のルールがありました。全員で円陣を組み、「3人ごとに1人」を殺していく手順を繰り返し、最後に残った1人が自害して終わるというものです。

しかし、最後まで生き残ったのはヨセフスともう1人の2人でした。この逸話の詳細が今日まで伝わっていることを考えれば、お察しのとおり、彼らは当初の約束どおりには行動しなかったようです。

ヨセフス順列を求めるJavaScript関数

ここでの課題は、ヨセフス順列を返すJavaScript関数を作成することです。関数は、円形に並んでいるものとみなした要素の初期配列と、数える間隔kを受け取ります。そして先頭から数えてk番目ごとに要素を取り除き、取り除いた順に並べた配列を結果として返します。

例として、n=7、k=3の場合、josephus(7,3)は次のように動作します。

[1,2,3,4,5,6,7] — 初期状態
[1,2,4,5,6,7] => 3が数え上げられ、結果 [3] へ
[1,2,4,5,7] => 6が数え上げられ、結果 [3,6] へ
[1,4,5,7] => 2が数え上げられ、結果 [3,6,2] へ
[1,4,5] => 7が数え上げられ、結果 [3,6,2,7] へ
[1,4] => 5が数え上げられ、結果 [3,6,2,7,5] へ
[4] => 1が数え上げられ、結果 [3,6,2,7,5,1] へ
[] => 4が数え上げられ、結果 [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;
// i番目に取り除かれる要素の位置を求める再帰関数（メモ化付き）
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));

アルゴリズムのポイント：メモ化による効率化

この実装の核心は、再帰関数helperです。「i番目に取り除かれる要素の位置」を、ヨセフス問題の古典的な漸化式で求めています。

• i = 1 の場合：(k - 1) % n
• i > 1 の場合：(k + helper(n - 1, k, i - 1)) % n

さらに、引数(n, k, i)をキーとしたオブジェクトmapで計算済みの結果をキャッシュするメモ化を行うことで、同じ値を何度も再計算する無駄を省き、全体の計算量を大幅に抑えています。

出力結果

コンソールへの出力は次のとおりです。

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