পাইথনে একটি স্ট্রিং এর n-ম অভিধানিকভাবে স্থানান্তর খুঁজুন

ধরুন আমাদের একটি স্ট্রিং আছে যার দৈর্ঘ্য m, এবং এই স্ট্রিংটিতে শুধুমাত্র ছোট হাতের অক্ষর রয়েছে, আমাদের অভিধানিকভাবে স্ট্রিংটির n-ম স্থানান্তর খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি স্ট্রিং ="pqr", n =3 এর মত হয়, তাহলে আউটপুট হবে "qpr" কারণ সমস্ত পারমুটেশন [pqr, prq, qpr, qrp, rpq, rqp], সেগুলি সাজানো ক্রমে রয়েছে৷

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

• MAX_CHAR :=26

• MAX_FACT :=20

• ফ্যাক্টোরিয়াল :=আকারের একটি অ্যারে MAX_FACT

• ফ্যাক্টোরিয়ালস[0] :=1

• আমি 1 থেকে MAX_FACT রেঞ্জের জন্য, করুন

  • ফ্যাক্টোরিয়ালস[i] :=ফ্যাক্টোরিয়ালস[i - 1] * i

• size :=স্ট্রিং এর আকার

• সংঘটন :=MAX_CHAR আকারের একটি অ্যারে, 0 দিয়ে পূরণ করুন

• আমি 0 থেকে আকারের রেঞ্জের জন্য, করুন

  • সংঘটন [ASCII of (string[i]) - ASCII of ('a') ] :=সংঘটন[ASCII of (string[i]) - ASCII of ('a') ] + 1

• res :=MAX_CHAR

  আকারের একটি অ্যারে

• যোগফল :=0, k :=0

• যখন যোগফল n এর মতো নয়, করুন

  • যোগফল :=0

  • আমি 0 থেকে MAX_CHAR রেঞ্জের জন্য, করুন

    • যদি সংঘটন[i] 0 এর মত হয়, তাহলে

      • পরবর্তী পুনরাবৃত্তির জন্য যান

    • সংঘটন[i] :=সংঘটন[i] - 1

    • temp_sum :=ফ্যাক্টোরিয়ালস [আকার - 1 - k]

    • 0 থেকে MAX_CHAR পরিসরে j এর জন্য, করুন

      • temp_sum :=temp_sum / factorials[ঘটনা[j]] (পূর্ণসংখ্যা বিভাগ)

    • যোগফল :=যোগফল + temp_sum

    • যদি যোগফল>=n হয়, তাহলে

      • res[k] :=ASCII কোড থেকে অক্ষর (i + ASCII of('a'))

      • n :=n - যোগফল - temp_sum

      • k :=k + 1

      • লুপ থেকে বেরিয়ে আসুন

    • যদি যোগফল

      • সংঘটন[i] :=সংঘটন[i] + 1

• i :=MAX_CHAR-1

• যখন k =0, do

  • যদি ঘটনা[i] অ-শূন্য হয়, তাহলে

    • res[k] :=ASCII কোড থেকে অক্ষর (i + ASCII of('a'))

    • সংঘটন[i] :=সংঘটন[i] - 1

    • i :=i + 1

    • k :=k + 1

  • i :=i - 1

• রিটার্ন মেক স্ট্রিং রেস থেকে ইনডেক্স 0 থেকে (k - 1)

উদাহরণ

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

MAX_CHAR = 26
MAX_FACT = 20
factorials = [None] * (MAX_FACT)
def get_nth_permute(string, n):
   factorials[0] = 1
   for i in range(1, MAX_FACT):
      factorials[i] = factorials[i - 1] * i
   size = len(string)
   occurrence = [0] * (MAX_CHAR)
   for i in range(0, size):
      occurrence[ord(string[i]) - ord('a')] += 1
   res = [None] * (MAX_CHAR)
   Sum = 0
   k = 0
   while Sum != n:
      Sum = 0
      for i in range(0, MAX_CHAR):
         if occurrence[i] == 0:
            continue
         occurrence[i] -= 1
         temp_sum = factorials[size - 1 - k]
         for j in range(0, MAX_CHAR):
            temp_sum = temp_sum // factorials[occurrence[j]]
         Sum += temp_sum
         if Sum >= n:
            res[k] = chr(i + ord('a'))
            n -= Sum - temp_sum
            k += 1
            break
         if Sum < n:
            occurrence[i] += 1
   i = MAX_CHAR-1
   while k < size and i >= 0:
      if occurrence[i]:
         res[k] = chr(i + ord('a'))
         occurrence[i] -= 1
         i += 1
         k += 1
      i -= 1
   return ''.join(res[:k])

n = 3
string = "pqr"
print(get_nth_permute(string, n))

ইনপুট

"pqr"

আউটপুট

qpr