Hoán vị

Nguồn: CLUE OJ – Chương 20: Quay lui (Backtracking) Độ khó: Dễ Quay lui 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$.

Ví dụ – input

3

Ví dụ – output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Lờ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ộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ testn tới 10!Ý tưởngcây quay luiCách 1quay luiCách 2next_permutationCách 3bộ đệm xuất

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

Lưu ý: đề ghi sai giới hạn

Đề ghi $1 \le N \le 8$ nhưng test 9 có $n = 9$ và test 10 có $n = 10$. Với $n = 10$, output nặng khoảng 83 MB, nên cách in bình thường bằng 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:

n =

Ví dụ nhanh:

Cách 1Quay lui + in bằng cout

C++▶ Chạy tay từng dòng codeCách 1: quay lui với mảng used[], in bằng cout.

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

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!)$.

Không gian$O(n)$

Thời gian$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.

C++▶ Chạy tay từng dòng codeCách 2: bắt đầu từ 1 2 ... n, gọi next_permutation để sang hoán vị kế tiếp.

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$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.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.

C++▶ Chạy tay từng dòng codeCách 3: quay lui như cũ nhưng ghi vào bộ đệm buf, cuối cùng fwrite một lần.

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• buf[len++] = '0' + v % 10; – ghi chữ số hàng đơn vị của $v$ rồi tăng len.
• Kiểm tra len > (1 << 16) - 100 ngay 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ớ fwrite phần còn lại – quên dòng này là mất các dòng cuối!

Không gian$O(n)$ + bộ đệm 64 KB

Thời gian$O(n \cdot n!)$

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++.

Ghi chú của mình: chỉ Cách 3 đạt 10/10 test; Cách 1 và Cách 2 đúng hết các test $n \le 8$ (đúng giới hạn đề ghi) nhưng quá thời gian ở test $n = 10$. Bài học: khi output lên tới hàng chục MB, hãy nghĩ tới tự gom bộ đệm rồi ghi một lần.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇