একটি ধনাত্মক পূর্ণ সংখ্যার সেটের একাধিক পার্টিশন কিভাবে করবো, যাতে সবগুলো পার্টিশনে রাখা সংখ্যাগুলোর যোগফল সমান হয়। নোটঃ প্রত্যেকটা পার্টিশনে একই সংখ্যক সংখ্যা থাকতে হবে এমন কোন বাধ্যবাধকতা নেই। উদাহরণস্বরূপঃ একটি সেট {২,৫,১,৩,৩,৭} এর তিনটি পার্টিশন হয় (২,৫), (১,৩,৩) এবং (৭) । আমি অনেক রিসোর্স খুঁজেছি। কিন্তু শুধুমাত্র দুইটি পার্টিশনের জন্য রিসোর্স পেয়েছি। ধন্যবাদ।

asked 28 Sep, 15:16

Jafar95's gravatar image

Jafar95
214

edited 08 Oct, 12:35

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
3115


এটি ব্যাকট্র্যাকিং দিয়ে সমাধান করা যায়। তবে আমাদেরকে আগে ঠিক করতে হবে যে মোট কয়টি পার্টিশন হবে। সেটা যদি জানা থাকে তবে আমরা প্রতিটা পার্টিশন এর সংখ্যা গুলোর যোগফল কত তা বের করতে পারব। এখন আমরা যদি একটা রিকার্শন/ব্যাকট্র্যাকিং চালাই তাহলে আমরা সবকয়টি পার্টিশন বের করতে পারব। আমরা সবকটি সংখ্যা থেকে কয়েকটি বের করব যাদের যোগফল পার্টিশন এর যত যোগফল হবার কথা তার সমান হয়। এটি O(2^n) এ করা যায়। তবে আমাদের কে প্রথম সংখ্যা তি অবশ্যই নিতে হবে। তা না হলে একি সেট বার বার আসবে। এরপরে এই সংখ্যা গুলোকে বাদ দিয়ে বাকি সংখ্যা গুলোর উপরে আবার একি কাজ করতে হবে, এবং প্রতিবারে আমাদের খেয়াল রাখতে হবে যাতে প্রথম সংখ্যাটিকে অবশ্যই নেয়া হয় এবং প্রতিবারে কোন সংখ্যা গুলো নিয়েছি তা খেয়াল রাখতে হবে। এরপরে বার বার করতে করতে যখন আর কোন সংখ্যা থাকবে না তখন শেষ করতে হবে। এবং প্রতিবারে যেসব সংখ্যা গুলো নিয়েছিলাম তাদের কে আমরা উপযুক্ত পার্টিশন হিসাবে পাব।

permanent link

answered 09 Oct, 14:33

nfssdq's gravatar image

nfssdq
312

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×35
×25
×23
×2
×1

question asked: 28 Sep, 15:16

question was seen: 60 times

last updated: 09 Oct, 14:33