โปรแกรมค้นหาจำนวนการดำเนินการขั้นต่ำในการจัดเรียงสตริงใน Python

สมมติว่าเรามีสตริง s เราต้องดำเนินการต่อไปนี้บน s จนกว่าเราจะได้สตริงที่เรียงลำดับ -

• เลือกดัชนีที่ใหญ่ที่สุด i โดยที่ 1 <=i <ความยาวของ s และ s[i]

• เลือกดัชนีที่ใหญ่ที่สุด j โดยที่ i <=j <ความยาวของ s และ s[k]

• แลกเปลี่ยนอักขระสองตัวที่ดัชนี i - 1 และ j.

• กลับคำต่อท้ายจากดัชนี i.

เราต้องหาจำนวนการดำเนินการที่จำเป็นในการจัดเรียงสตริง คำตอบอาจมีขนาดใหญ่มาก ดังนั้นส่งคืนผลลัพธ์ modulo 10^9 + 7.

ดังนั้น หากอินพุตเป็น s ="ppqpp" ผลลัพธ์จะเป็น 2 เพราะ

• ในการดำเนินการครั้งแรก i=3, j=4 แลกเปลี่ยน s[2] และ s[4] เพื่อรับ s="ppppq" จากนั้นย้อนกลับสตริงย่อยจากดัชนี 3 ตอนนี้ s="pppqp"

• ในการดำเนินการที่สอง i=4, j=4 แลกเปลี่ยน s[3] และ s[4] เพื่อรับ s="ppppq" จากนั้นกลับสตริงย่อยจากดัชนี 4 ตอนนี้ s ="ppppq"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• d :=อาร์เรย์ขนาด 26 และเติม 0

• ก :=0, t :=1

• ม :=10^9 + 7

• n :=ASCII ของ 'a'

• สำหรับแต่ละดัชนี i และอักขระ c ของ s ในลำดับย้อนกลับ เริ่มต้นดัชนีจาก 1 ทำ

  • j :=ASCII ของ c - n

  • 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