पायथन में एक स्ट्रिंग के n-वें लेक्सिकोग्राफिक रूप से क्रमपरिवर्तन का पता लगाएं

मान लीजिए कि हमारे पास एक स्ट्रिंग है जिसकी लंबाई m है, और इस स्ट्रिंग में केवल लोअरकेस अक्षर हैं, हमें स्ट्रिंग के n-th क्रमपरिवर्तन को लेक्सिकोग्राफ़िक रूप से खोजना होगा।

इसलिए, यदि इनपुट स्ट्रिंग ="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

• आकार :=स्ट्रिंग का आकार

• घटना :=MAX_CHAR आकार की एक सरणी, 0 से भरें

• मेरे लिए 0 से आकार की सीमा में, ऐसा करें

  • घटना [एएससीआईआई (स्ट्रिंग [i]) - एएससीआईआई ('ए')]:=घटना [एएससीआईआई (स्ट्रिंग [i]) - एएससीआईआई ('ए')] + 1

• res :=आकार की एक सरणी MAX_CHAR

• योग:=0, कश्मीर:=0

• जबकि योग n के समान नहीं है, करें

  • योग :=0

  • मेरे लिए 0 से MAX_CHAR की सीमा में, करें

    • अगर घटना [i] 0 के समान है, तो

      • अगले पुनरावृत्ति के लिए जाएं

    • घटना[i] :=घटना[i] - 1

    • temp_sum :=फैक्टोरियल्स [आकार - 1 - k]

    • j के लिए 0 से MAX_CHAR की सीमा में, करें

      • temp_sum :=temp_sum / फैक्टोरियल्स [घटना [j]] (पूर्णांक विभाजन)

    • योग :=योग + temp_sum

    • यदि योग>=n, तो

      • res[k] :=ASCII कोड से वर्ण (i + ASCII of('a'))

      • n:=n - योग - temp_sum

      • कश्मीर:=के + 1

      • लूप से बाहर आएं

    • अगर योग

      • घटना [i] :=घटना[i] + 1

• मैं :=MAX_CHAR-1

• जबकि k =0, do

  • अगर घटना [i] शून्य नहीं है, तो

    • res[k] :=ASCII कोड से वर्ण (i + ASCII of('a'))

    • घटना[i] :=घटना[i] - 1

    • मैं :=मैं + 1

    • कश्मीर:=के + 1

  • मैं :=मैं - 1

• इंडेक्स 0 से (के -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