Python में स्ट्रिंग का nth लेक्सिकोग्राफिक क्रमपरिवर्तन ढूंढना

मान लीजिए हमारे पास एक स्ट्रिंग है जिसकी लंबाई m है, और यह स्ट्रिंग केवल लोअरकेस अक्षरों को समाहित करती है, हमें स्ट्रिंग का nth क्रमपरिवर्तन लेक्सिकोग्राफिक रूप से ढूंढना है।

तो, यदि इनपुट स्ट्रिंग = "pqr", n = 3 की तरह है, तो आउटपुट "qpr" होगा क्योंकि सभी क्रमपरिवर्तन [pqr, prq, qpr, qrp, rpq, rqp] हैं, वे क्रमबद्ध क्रम में हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• MAX_CHAR := 26

• MAX_FACT := 20

• factorials := MAX_FACT आकार की एक सरणी

• factorials[0] := 1

• i के लिए 1 से MAX_FACT की सीमा में, करें

  • factorials[i] := factorials[i - 1] * i

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

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

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

  • occurrence[ASCII of (string[i]) - ASCII of ('a')] := occurrence[ASCII of (string[i]) - ASCII of ('a')] + 1

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

• Sum := 0, k := 0

• जब तक Sum, n के समान नहीं है, करें

  • Sum := 0

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

    • यदि occurrence[i], 0 के समान है, तो

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

    • occurrence[i] := occurrence[i] - 1

    • temp_sum := factorials[size - 1 - k]

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

      • temp_sum := temp_sum / factorials[occurrence[j]] (पूर्णांक विभाजन)

    • Sum := Sum + temp_sum

    • यदि Sum >= n, तो

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

      • n := n - Sum - temp_sum

      • k := k + 1

      • लूप से बाहर निकलें

    • यदि Sum < n, तो

      • occurrence[i] := occurrence[i] + 1

• i := MAX_CHAR-1

• जब k < size और i >= 0, करें

  • यदि occurrence[i] शून्येतर है, तो

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

    • occurrence[i] := occurrence[i] - 1

    • i := i + 1

    • k := k + 1

  • i := i - 1

• इंडेक्स 0 से (k - 1) तक res से स्ट्रिंग बनाकर लौटाएं

उदाहरण

बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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