โปรแกรมหาจำนวนการสลับเพื่อเรียงอาร์เรย์ใน Python

สมมติว่ามีอาร์เรย์ nums ต้องหาจำนวนการสลับ (swap) น้อยที่สุดเพื่อเรียงลำดับ nums ให้เรียงได้ทั้งจากน้อยไปมากหรือมากไปน้อย

ตัวอย่าง: nums = [2,5,6,3,4] ผลลัพธ์ 2 เพราะสลับ 6↔4 ได้ [2,5,4,3,6] แล้วสลับ 5↔3 ได้ [2,3,4,5,6]

วิธีแก้ปัญหา

1. ฟังก์ชัน swap_count(input_arr):
   • pos := sorted(enumerate(input_arr), key=lambda x: x[1])
   • cnt := 0
   • วน index ทุกค่า:
     • while True: ถ้า pos[index][0] == index break มิฉะนั้นสลับ pos[index] กับ pos[swap_index], cnt += 1
   • คืน cnt
2. คืน min(swap_count(arr), swap_count(arr[::-1]))

ตัวอย่างโค้ด

def swap_count(input_arr):
    pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
    cnt = 0
    for index in range(len(input_arr)):
        while True:
            if pos[index][0] == index:
                break
            else:
                cnt += 1
                swap_index = pos[index][0]
                pos[index], pos[swap_index] = pos[swap_index], pos[index]
    return cnt

def solve(input_arr):
    return min(swap_count(input_arr), swap_count(input_arr[::-1]))

nums = [2,5,6,3,4]
print(solve(nums))

อินพุต

[2, 5, 6, 3, 4]

เอาต์พุต

2