การคำนวณ Josephus Permutations อย่างมีประสิทธิภาพใน JavaScript

ปัญหานี้ได้ชื่อมาจากเหตุการณ์สำคัญในชีวิตของนักประวัติศาสตร์โบราณ Josephus ตามเรื่องราวของเขา เขาและทหาร 40 คนติดอยู่ในถ้ำถูกโรมันล้อมรอบ

ไม่ยอมสละ พวกเขาเลือกฆ่าตัวตายแบบมีเงื่อนไข: จัดวงกลมและฆ่าทุก 3 คน จนเหลือคนสุดท้าย (ซึ่งควรกลายเป็นผู้ฆ่าตัวตายคนสุดท้าย)

Josephus และอีกคนหนึ่งเป็นคนสุดท้ายสองคน และเรารู้ว่าพวกเขาไม่ได้ทำตามแผนเดิม

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่คืน Josephus permutation

รับพารามิเตอร์เป็นอาร์เรย์เริ่มต้นของรายการ (สมมติว่าอยู่ในวงกลม) และนับทุก 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
]