Chương trình tìm số lần hoán vị tối thiểu để sắp xếp mảng trong Python

Mô tả bài toán

Cho mảng nums. Hãy tìm số lần hoán vị (swap) tối thiểu để sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần.

Ví dụ

Nếu nums = [2, 5, 6, 3, 4], đầu ra là 2 vì: hoán vị 6 và 4 -> [2,5,4,3,6], rồi hoán vị 5 và 3 -> [2,3,4,5,6].

Giải thuật

1. Hàm swap_count(arr): tạo danh sách cặp (index, value), sắp xếp theo value. Duyệt qua các vị trí, hoán vị cho đến khi phần tử đúng vị trí, đếm số lần swap.
2. Trả về min của swap_count(nums) và swap_count(nums[::-1]).

Triển khai Python

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))

Đầu vào

[2, 5, 6, 3, 4]

Đầu ra

2