पायथन में स्ट्रिंग को क्रमबद्ध करने के लिए न्यूनतम संख्या में संचालन खोजने का कार्यक्रम

हमें स्ट्रिंग को सॉर्ट करने के लिए आवश्यक संचालन की संख्या का पता लगाना होगा। उत्तर बहुत बड़ा हो सकता है इसलिए वापसी परिणाम मॉड्यूल 10^9 + 7.

इसलिए, यदि इनपुट s ="ppqpp" जैसा है, तो आउटपुट 2 होगा क्योंकि

• पहले ऑपरेशन में, i=3, j=4. s="ppppq" प्राप्त करने के लिए s[2] और s[4] का आदान-प्रदान करें, फिर इंडेक्स 3 से सबस्ट्रिंग को उलट दें। अब, s="pppqp"।

• दूसरे ऑपरेशन में, i=4, j=4. s[3] और s[4] को s="ppppq" प्राप्त करने के लिए एक्सचेंज करें, फिर इंडेक्स 4 से सबस्ट्रिंग को उलट दें, अब, s ="ppppq"।

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

• d :=26 आकार की एक सरणी और 0 से भरें

• ए:=0, टी:=1

• मी :=10^9 + 7

• n :='a' का ASCII

• प्रत्येक अनुक्रमणिका i और s के वर्ण c के लिए उल्टे क्रम में, 1 से अनुक्रमणिका प्रारंभ करें, करें

  • j :=c - n का ASCII

  • d[j] :=d[j] + 1

  • a :=(a + d के सभी तत्वों का योग [सूचकांक 0 से j-1 तक]) * t/d[j] का भागफल) mod m

  • t :=t * i/d[j]

    . का भागफल

• वापसी एक

उदाहरण

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

def solve(s):
   d = [0]*26
   a = 0
   t = 1
   m = 10**9 + 7
   n = ord('a')
   for i,c in enumerate(s[::-1],1):
      j = ord(c) - n
      d[j] += 1
      a = (a+sum(d[:j])*t//d[j]) % m
      t = t*i//d[j]
   return a

s = "ppqpp"
print(solve(s))

इनपुट

"ppqpp"

आउटपुट

2