Hoán vị
Đề bài
Trong lý thuyết tổ hợp, khái niệm hoán vị mô tả một bộ có thứ tự không lặp: những đối tượng phân biệt có thể được sắp xếp theo những thứ tự khác nhau. Cho tập hợp $A$ gồm $n$ phần tử $(n \ge 1)$. Mỗi kết quả của sự sắp xếp thứ tự $n$ phần tử của tập hợp $A$ được gọi là một hoán vị của $n$ phần tử đó. Ví dụ: $A = \{1, 2, 3\}$, một trong những hoán vị của $A$ là $3, 2, 1$.
Trong bài tập này bạn được cho một tập $A$ gồm $n$ phần tử là các số nguyên từ $1$ đến $n$. Bạn hãy liệt kê tất cả các hoán vị của tập $A$.
Dữ liệu vào: gồm một số nguyên dương $N$ duy nhất.
Kết quả: mỗi dòng ghi một hoán vị của tập $A$. Các hoán vị được liệt kê theo thứ tự từ điển.
Ràng buộc: $1 \le N \le 8$.
31 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1Lời mở đầu
Hoán vị chính là chỉnh hợp chập $n$ của $n$, nên ý tưởng quay lui + mảng used[] dùng lại y nguyên. Điều thú vị của bài nằm ở bộ test: đề ghi $N \le 8$ nhưng bộ test thật có cả $n = 9$ và $n = 10$ – tức là phải in ra $3.628.800$ dòng, hơn 80 MB! Lúc này thuật toán không còn là vấn đề, mà tốc độ in mới quyết định. Mình sẽ đi 3 cách và chạy thật cả 3.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | n | Số dòng $n!$ | Dung lượng output |
|---|---|---|---|
| 1 | 3 | 6 | 0 KB |
| 2 | 2 | 2 | 0 KB |
| 3 | 1 | 1 | 0 KB |
| 4 | 4 | 24 | 0 KB |
| 5 | 5 | 120 | 1 KB |
| 6 | 6 | 720 | 10 KB |
| 7 | 7 | 5.040 | 81 KB |
| 8 | 8 | 40.320 | 726 KB |
| 9 | 9 | 362.880 | 7,3 MB |
| 10 | 10 | 3.628.800 | 83,5 MB |
cout bị quá thời gian. Mình chia thành 2 mức như sau:| Mức | Điều kiện | Các test | Cách 1 quay lui + cout | Cách 2 next_permutation | Cách 3 quay lui + bộ đệm |
|---|---|---|---|---|---|
| 1 | $n \le 8$ | 1 – 8 | 8/8 | 8/8 | 8/8 |
| 2 | $n = 9, 10$ | 9 – 10 | 1/2 | 1/2 | 2/2 |
(Số liệu chạy thật bản C++, giới hạn 1 giây/test.)
Ý tưởngCây quay lui của hoán vị
Try(i) chọn số cho vị trí $i$: thử $v = 1..n$, bỏ qua số đã dùng (used[v] = true), chọn thì đánh dấu, đi tiếp, rồi bỏ đánh dấu khi quay lui. Tới $i = n$ là có một hoán vị. Vì thử $v$ từ nhỏ đến lớn nên kết quả ra đúng thứ tự từ điển. Số lá của cây đúng bằng $n!$.
Em nhập $n$ (tối đa 3) rồi bấm Tiếp để xem từng bước. Nút đỏ ✗ là số bị bỏ qua vì đã dùng:
Cách 1Quay lui + in bằng cout
Code y hệt bài Chỉnh hợp, chỉ thay $k$ bằng $n$. Mỗi lần gọi Try thử $n$ số nên tổng thời gian khoảng $O(n \cdot n!)$.
Kết quả chạy thật: C++: đúng 9/10 test, quá thời gian ở test 10 (mất 1.77 giây, giới hạn 1 giây); các test còn lại chậm nhất 0.144 giây. Bản Python: Python: đúng 9/10 test, quá thời gian ở test 10 (mất 3.76 giây, giới hạn 1 giây); các test còn lại chậm nhất 0.606 giây.
Thuật toán không có gì sai: $n \cdot n! \approx 3,6 \cdot 10^7$ phép toán thì máy chạy chưa tới 0,1 giây. Thời gian bị tiêu vào việc in 3,6 triệu dòng bằng cout << x[j] << ' ' – mỗi lần in một số đều phải đổi số ra chữ và gọi qua lớp stream của C++.
Cách 2Dùng next_permutation có sẵn
Thư viện C++ có hàm next_permutation: biến dãy thành hoán vị kế tiếp theo thứ tự từ điển, trả về false khi dãy đã là hoán vị lớn nhất. Bắt đầu từ 1 2 ... n rồi gọi liên tục là được đủ $n!$ hoán vị theo đúng thứ tự.
Hàm này làm 3 việc: (1) từ phải sang tìm vị trí $p$ đầu tiên có $a_p < a_{p+1}$ (đoạn sau $p$ đang giảm dần); (2) tìm từ phải sang số $a_q$ đầu tiên lớn hơn $a_p$ rồi đổi chỗ $a_p, a_q$; (3) đảo ngược đoạn sau $p$. Ví dụ 1 3 2: $p = 0$ (vì $1 < 3$), $a_q = 2$, đổi thành 2 3 1, đảo đoạn sau thành 2 1 3.
Kết quả chạy thật: C++: đúng 9/10 test, quá thời gian ở test 10 (mất 1.61 giây, giới hạn 1 giây); các test còn lại chậm nhất 0.142 giây. Bản Python (itertools.permutations): Python: đúng 9/10 test, quá thời gian ở test 10 (mất 3.31 giây, giới hạn 1 giây); các test còn lại chậm nhất 0.345 giây.
Nhanh hơn Cách 1 một chút nhưng vẫn quá thời gian ở test 10 – đúng như dự đoán: thủ phạm là phần in chứ không phải phần sinh hoán vị.
Cách 3Quay lui + tự gom vào bộ đệm
Ta vẫn giữ nguyên quay lui của Cách 1, chỉ thay cách in: tự chuyển mỗi số thành ký tự và ghi vào mảng buf; khi bộ đệm gần đầy (khoảng 64 KB) thì đổ ra màn hình một lần bằng fwrite. Vì các số chỉ từ 1 đến 10 nên đổi số ra chữ rất đơn giản: số có 2 chữ số chỉ có thể là 10.
buf[len++] = '0' + v % 10;– ghi chữ số hàng đơn vị của $v$ rồi tănglen.- Kiểm tra
len > (1 << 16) - 100ngay sau mỗi dòng: một dòng dài tối đa 21 ký tự nên bộ đệm không bao giờ bị tràn. - Cuối chương trình phải nhớ
fwritephần còn lại – quên dòng này là mất các dòng cuối!
Kết quả chạy thật: C++: đúng 10/10 test, test chậm nhất chạy 0.231 giây. Bản Python: Python: đúng 10/10 test, test chậm nhất chạy 0.919 giây. Bản Python này dùng itertools.permutations trên các chuỗi số có sẵn và ghi theo từng khối 200.000 dòng – vừa đủ lọt giới hạn, nhưng khá sát nên các bạn ưu tiên C++.