Cặp nghịch đảo là cặp chỉ số
Với hai vị trí `i < j`, cặp đó là **nghịch đảo** nếu `a[i] > a[j]`. Trước hết liệt kê mọi cặp vị trí bên trái–bên phải; sau đó giữ lại cặp có giá trị bên trái lớn hơn. Hai giá trị bằng nhau **không** tạo nghịch đảo. Ví dụ `a = [3, 2, 1, 5, 4]` có bốn cặp theo giá trị: `(3,2)`, `(3,1)`, `(2,1)`, `(5,4)`. Nếu có giá trị trùng, cần nói cặp theo **chỉ số** để phân biệt những lần xuất hiện.
Mỗi cặp i < j được xét đúng một lần
```python
def dem_nghich_dao(a):
dem = 0
for i in range(len(a) - 1):
for j in range(i + 1, len(a)):
if a[i] > a[j]:
dem += 1
return dem
print(dem_nghich_dao([3, 2, 1, 5, 4]))
```
Kết quả là `4`. Vòng trong bắt đầu ở `i + 1` để luôn có `i < j`; nếu bắt đầu cố định từ 1 thì có thể xét cả cặp sai chiều và đếm trùng. Dãy đã không giảm có 0 nghịch đảo. Dãy ba số giảm hẳn `[3, 2, 1]` có 3 nghịch đảo.
Bài luyện
Với `a = [2, 2, 1]`, có bao nhiêu cặp nghịch đảo?
Mỗi số 2 đứng trước 1 tạo một cặp.
Còn một số 2 nữa đứng trước 1.
Hai cặp chỉ số (0,2) và (1,2).
Hai số 2 bằng nhau không tạo nghịch đảo.
Lời giải
Các cặp (0,2) và (1,2) có 2 > 1; cặp (0,1) có 2 = 2 nên không tính.
Bài luyện
Trong mã đếm nghịch đảo, vì sao vòng trong dùng `range(i + 1, len(a))`?
Điều kiện định nghĩa cần i < j.
j bằng i không phải cặp hai vị trí.
range vẫn đến len(a)-1.
Chỉ số không phụ thuộc dấu của giá trị.
Lời giải
j bắt đầu tại i+1 và chạy đến vị trí cuối, nên đúng mọi cặp i<j được xét một lần.
Bài luyện
`dem_nghich_dao([3, 2, 1, 5, 4])` trả gì?
Còn thiếu cặp (5,4).
Các cặp là (3,2), (3,1), (2,1), (5,4).
3 không lớn hơn 4 hoặc 5.
10 là tổng mọi cặp chỉ số, không phải số nghịch đảo.
Lời giải
Trong 10 cặp chỉ số i<j, đúng bốn cặp có giá trị ở trước lớn hơn giá trị ở sau.
Đang học