Tính toán các phép hoán vị Josephus một cách hiệu quả trong JavaScript

Vấn đề này được đặt tên theo sự kiện được cho là quan trọng nhất trong cuộc đời của nhà sử học cổ đại Josephus - theo câu chuyện của ông, ông và 40 người lính của mình đã bị mắc kẹt trong một hang động bởi người La Mã trong một cuộc bao vây.

Không chịu đầu hàng kẻ thù, thay vào đó, họ chọn cách tự sát hàng loạt, với một vòng xoắn - họ tạo thành một vòng tròn và tiến hành giết một người đàn ông cứ mỗi ba người, cho đến khi còn lại một người đàn ông cuối cùng (và phải tự sát để kết thúc hành động ).

Josephus và một người đàn ông khác là hai người cuối cùng và như bây giờ chúng ta đã biết mọi chi tiết của câu chuyện, bạn có thể đoán chính xác rằng họ không theo đúng ý tưởng ban đầu.

Chúng tôi bắt buộc phải viết một hàm JavaScript trả về một hoán vị Josephus.

Lấy làm tham số, mảng / danh sách các mục ban đầu được hoán vị như thể chúng nằm trong một vòng tròn và đếm ra từng k vị trí cho đến khi không còn vị trí nào.

Ví dụ:với n =7 và k =3 josephus (7,3) nên hành động theo cách này.

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

Do đó, kết quả cuối cùng của chúng tôi là -

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

Ví dụ

Mã cho điều này sẽ là -

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

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

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