Tính hoán vị Josephus hiệu quả trong JavaScript

Vấn đề Josephus: n người đứng thành vòng, loại người thứ k cho đến khi còn 1 người. Trả về thứ tự bị loại.

Ví dụ n=7, k=3: [1,2,3,4,5,6,7] → loại 3,6,2,7,5,1,4 → kết quả [3,6,2,7,5,1,4].

Ví dụ

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));

Kết quả

Kết quả in ra console:

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