এই সমস্যাটি প্রাচীন ইতিহাসবিদ জোসেফাসের জীবনের সবচেয়ে গুরুত্বপূর্ণ ঘটনা বলে এর নাম নেয় - তার গল্প অনুসারে, তিনি এবং তার 40 জন সৈন্য রোমানদের দ্বারা একটি গুহায় আটকা পড়েছিলেন একটি অবরোধ।
শত্রুর কাছে আত্মসমর্পণ করতে অস্বীকার করে, তারা পরিবর্তে গণ-আত্মহত্যার পথ বেছে নেয়, একটি মোচড় দিয়ে - তারা একটি বৃত্ত তৈরি করে এবং প্রতি তিনজনে একজনকে হত্যা করতে এগিয়ে যায়, যতক্ষণ না একজন শেষ ব্যক্তি অবশিষ্ট থাকে (এবং এই কাজটি শেষ করতে আত্মহত্যা করার কথা ছিল) )।
জোসেফাস এবং অন্য একজন মানুষ ছিলেন শেষ দুজন এবং, আমরা এখন গল্পের প্রতিটি বিশদ বিবরণ জানি, আপনি সঠিকভাবে অনুমান করতে পারেন যে তারা আসল ধারণাটি ঠিক অনুসরণ করেননি।
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা জোসেফাস পারমুটেশন প্রদান করে।
প্যারামিটার হিসাবে গ্রহণ করা আইটেমগুলির প্রারম্ভিক অ্যারে/তালিকাকে অনুমতি দেওয়া হয় যেন তারা একটি বৃত্তের মধ্যে থাকে এবং প্রতিটি k স্থান গণনা করে যতক্ষণ না কোনওটি অবশিষ্ট না থাকে।
উদাহরণস্বরূপ, n=7 এবং k=3 জোসেফাস(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 ]
