পাইথনে অভিধানিকভাবে সবচেয়ে বড় বৈধ ক্রম নির্মাণের জন্য প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা n আছে, আমাদের একটি ক্রম খুঁজে বের করতে হবে যা নিম্নলিখিত সমস্ত নিয়মগুলিকে সন্তুষ্ট করে −

• 1 অনুক্রমের মধ্যে একবার ঘটে।

• 2 এবং n এর মধ্যে প্রতিটি সংখ্যা ক্রমানুসারে দুবার আসে।

• 2 থেকে n পরিসরের প্রতিটি i-এর জন্য, i-এর দুটি ঘটনার মধ্যে দূরত্ব ঠিক i৷

অনুক্রমের দুটি সংখ্যার মধ্যে দূরত্ব, a[i] এবং a[j], হল |j - i|। আমাদের আভিধানিকভাবে সবচেয়ে বড় ক্রম খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট n =4 এর মত হয়, তাহলে আউটপুট হবে [4, 2, 3, 2, 4, 3, 1]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন ব্যাকট্র্যাক() সংজ্ঞায়িত করুন। এটি elems, res, start :=0
লাগবে
• যদি এলিমের আকার <=0 হয়, তাহলে
  • সত্য ফেরান
• যদি start>=res এর সাইজ হয়, তাহলে
  • মিথ্যে ফেরত দিন
• যদি res[start] -1 এর মত না হয়, তাহলে
  • রিটার্ন ব্যাকট্র্যাক(elems, res, start + 1)
• এর জন্য আমি 0 থেকে এলিমের আকার - 1 এর মধ্যে, কর
  • সংখ্যা :=এলেম[i]
  • dist :=0 যখন num একই হয় 1 অন্যথায় num
  • যদি (start + dist)
  • res[start] :=সংখ্যা
  • res[start + dist] :=সংখ্যা
  • elems থেকে ith উপাদান মুছুন
  • যদি backtrack(elems, res, start) মিথ্যা হয়, তাহলে
    • res[start] :=-1
    • res[start + dist] :=-1
    • পজিশন i এ এলেমগুলিতে num সন্নিবেশ করান
    • পরবর্তী পুনরাবৃত্তির জন্য যান
  • অন্যথায়,
    • সত্য ফেরান

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def backtrack(elems, res, start = 0):
   if len(elems) <= 0:
      return True

   if start >= len(res):
      return False

   if res[start] != -1:
      return backtrack(elems, res, start + 1)

   for i in range(len(elems)):
      num = elems[i]
      dist = 0 if num == 1 else num

      if (start + dist) < len(res) and res[start + dist] == -1:
         res[start] = num
         res[start + dist] = num
         elems.pop(i)

         if not backtrack(elems, res, start):
            res[start] = -1
            res[start + dist] = -1
            elems.insert(i, num)
            continue
         else:
            return True
def solve(n):
   elems = [ i for i in range(n,0,-1)]
   res = [ -1 for i in range(n*2 - 1)]
   backtrack(elems, res)
   return res

n = 4
print(solve(n))

ইনপুট

4

আউটপুট

[4, 2, 3, 2, 4, 3, 1]