কে পাইথনের আকার 1 থেকে n পর্যন্ত kth লেক্সিকোগ্রাফিক ক্রম খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের দুটি মান আছে n এবং k। এখন 1 থেকে n [1, 2, ..., n] রেঞ্জের সংখ্যার একটি তালিকা বিবেচনা করুন এবং এই তালিকার প্রতিটি স্থানান্তরকে অভিধানিক ক্রমানুসারে তৈরি করুন। উদাহরণস্বরূপ, যদি n =4 আমাদের আছে [1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 324, 324, 324, 324, 324 4213, 4231, 4312, 4321]। আমাদের একটি স্ট্রিং হিসাবে এই স্থানান্তর ক্রমটির kth মান খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট n =4 k =5 এর মত হয়, তাহলে আউটপুট হবে "1432"

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

একটি ফাংশন ফ্যাক্টর () সংজ্ঞায়িত করুন। এই সংখ্যা লাগবে
quo :=সংখ্যা
res :=একটি ডবল শেষ সারি এবং শুরুতে 0 ঢোকান
i :=2
quo খালি না থাকার সময়, করুন
- quo :=(quo / i), rem :=quo mod i
- res এর বাম দিকে rem ঢোকান
- i :=i + 1
রিটার্ন রিটার্ন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
সংখ্যা :=1 থেকে n
মান সহ একটি তালিকা
res :=ফাঁকা স্ট্রিং
k_fact :=ফ্যাক্টর(k)
যখন k_fact এর আকার <সংখ্যার আকার, করুন
- res :=res স্ট্রিং হিসাবে সংখ্যার প্রথম উপাদানকে সংযুক্ত করুন, তারপর সংখ্যার প্রথম উপাদান মুছে দিন
k_fact-এ প্রতিটি সূচকের জন্য, করুন
- সংখ্যা :=সূচক-সংখ্যার তম উপাদান, তারপর সেই উপাদানটি সরান
- res :=res concatenate number
রিটার্ন রিটার্ন

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

উদাহরণ

from collections import deque
def factors(num):
   quo = num
   res = deque([0])
   i = 2
   while quo:
      quo, rem = divmod(quo, i)
      res.appendleft(rem)
      i += 1
   return res
class Solution:
   def solve(self, n, k):
      numbers = [num for num in range(1, n + 1)]
      res = ""
      k_fact = factors(k)
      while len(k_fact) < len(numbers):
         res += str(numbers.pop(0))
      for index in k_fact:
         number = numbers.pop(index)
         res += str(number)
      return res
ob = Solution()
n = 4
k = 5
print(ob.solve(n, k))

ইনপুট

4, 5