โปรแกรมค้นหาจำนวนสับเปลี่ยนที่ต้องการเพื่อจัดเรียงองค์ประกอบของอาร์เรย์ใน Python

สมมติว่าเรามีชุดขององค์ประกอบจำนวน เราต้องเรียงลำดับตามลำดับที่ไม่ลดลง แต่เทคนิคการเรียงลำดับจะเป็นการสุ่ม เราจะตรวจสอบว่าอาร์เรย์ถูกจัดเรียงหรือไม่ ถ้าไม่ใช่ ให้สุ่มสุ่มแล้วตรวจสอบอีกครั้ง จนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง ให้ดำเนินการตามขั้นตอนนี้ต่อไป ในกรณีนี้ เราต้องหาจำนวนสับเปลี่ยนที่คาดไว้เพื่อจัดเรียง แสดงคำตอบได้สูงสุด 6 ตำแหน่ง

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[5,2,7] ผลลัพธ์จะเป็น 6 เนื่องจากมีการเปลี่ยนลำดับได้ 3 แบบ ดังนั้นความน่าจะเป็นคือ 1/3

• ถ้าเราเรียงอาร์เรย์ที่ i =1 จำนวนการวนซ้ำ ก็จะได้ 1/3
• ถ้าเราเรียงอาร์เรย์ที่ i =2 จำนวนการวนซ้ำ ก็จะใช้เวลา (2/3)*(1/3)

หากเราได้รับอาร์เรย์ที่เรียงลำดับตามจำนวนการวนซ้ำครั้งที่ i ก็จะใช้เวลา (2/3)^(i-1) * (1/3)

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

• ถ้าเรียงลำดับแล้ว
  • คืน 0
• มิฉะนั้น
  • m:=พจนานุกรมใหม่ว่างเปล่า
  • สำหรับแต่ละ i ใน nums ทำ
    • ถ้าฉันอยู่ใน m แล้ว
      • m[i] :=m[i] + 1
    • มิฉะนั้น
      • m[i]:=1
  • จำนวน:=1
  • สำหรับแต่ละคีย์ i ใน m ให้ทำ
    • num :=num * factorial(m[i])
  • den:=factorial(ขนาดของ nums)
  • ส่งคืน (den/num) และปัดเศษทศนิยมได้สูงสุด 6 ตำแหน่ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from math import factorial
def solve(nums):
   if nums == sorted(nums):
      return 0
   else:
      m={}
      for i in nums:
         if i in m:
            m[i]+=1
         else:
            m[i]=1
      num=1
      for i in m:
         num *= factorial(m[i])

      den=factorial(len(nums))
      return round((den/num),6)

nums = [5,2,7]
print(solve(nums))

อินพุต

[5,2,7]

ผลลัพธ์

6.0