Chỉnh hợp

Nguồn: CLUE OJ – Chương 20: Quay lui (Backtracking) Độ khó: Dễ Quay lui Mảng đánh dấu

Đề bài

Hãy in ra tất cả các chỉnh hợp chập $k$ của các số nguyên dương $1, 2, 3, \ldots, n$.

Chỉnh hợp là cách chọn những phần tử từ một nhóm lớn hơn và có phân biệt thứ tự.

Input: một dòng gồm hai số nguyên $n, k$.

Output: mỗi dòng gồm $k$ số nguyên là một chỉnh hợp. Các chỉnh hợp cần được in ra theo thứ tự từ điển.

Điều kiện: $1 \le k < n \le 7$.

Ví dụ – input

3 2

Ví dụ – output

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

Lời mở đầu

Chỉnh hợp chập $k$ của $n$ là một dãy $k$ số khác nhau lấy từ $1..n$, đổi thứ tự là thành chỉnh hợp khác (1 2 khác 2 1). Bài này dạy một kỹ thuật cực kỳ quan trọng của quay lui: mảng đánh dấu used[] – đánh dấu khi chọn, bỏ đánh dấu khi quay lui. Bài sau (Hoán vị) chính là trường hợp $k = n$ của bài này.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

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

Bộ test21 testÝ tưởngmảng used[]CodeC++ & Python

Bộ testBộ test chính thức có gì?

Bộ test có 21 test, phủ đủ mọi cặp $(n, k)$ với $2 \le n \le 7$, $1 \le k < n$:

n	Các test	Các giá trị k	Số dòng in ra $A_n^k$
2	1	1	2
3	2–3	1, 2	3, 6
4	4–6	1, 2, 3	4, 12, 24
5	7–10	1, 2, 3, 4	5, 20, 60, 120
6	11–15	1, 2, 3, 4, 5	6, 30, 120, 360, 720
7	16–21	1, 2, 3, 4, 5, 6	7, 42, 210, 840, 2.520, 5.040

Nhiều nhất là test $n = 7, k = 6$ với $7!/1! = 5040$ dòng – rất nhỏ. Bài không chia subtask; chỉ cần quay lui đúng là qua hết.

Ý tưởngChọn từng vị trí, số nào dùng rồi thì đánh dấu

Ta điền lần lượt $x_1, x_2, \ldots, x_k$. Hàm Try(i) chọn số cho vị trí $i$: thử $v = 1, 2, \ldots, n$, nhưng bỏ qua những số đã xuất hiện ở các vị trí trước. Để biết nhanh "số $v$ đã dùng chưa" (thay vì dò lại cả dãy), ta giữ mảng used[v]:

Ba bước của mỗi lựa chọn

Chọn: x[i] = v; used[v] = true; → Đi tiếp: đủ $k$ số thì in, chưa đủ thì Try(i + 1) → Quay lui: used[v] = false; để số $v$ được dùng lại ở các nhánh khác.

Thử $v$ từ nhỏ tới lớn ở mọi vị trí nên các chỉnh hợp ra đúng thứ tự từ điển. Em nhập $n, k$ (tối đa 4) rồi bấm Tiếp – nút đỏ ✗ là số bị bỏ qua vì đã dùng:

n = k =

Ví dụ nhanh:

CodeCài đặt

C++▶ Chạy tay từng dòng codeQuay lui: chọn số cho từng vị trí, đánh dấu used[] khi chọn và bỏ đánh dấu khi quay lui.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Dòng used[v] = false; là linh hồn của quay lui: thiếu nó thì sau chỉnh hợp đầu tiên, số 1 bị đánh dấu "đã dùng" mãi mãi và ta mất hết các chỉnh hợp có số 1 ở vị trí sau.
• Mảng used khai báo toàn cục nên ban đầu toàn false; mỗi lần đi xuống rồi quay lên, nó trở về đúng trạng thái cũ.
• Mỗi dòng in thừa một dấu cách ở cuối – không sao, trình chấm so sánh theo từng số.

Không gian$O(n)$

Thời gian$O(n \cdot A_n^k)$

Số nút của cây là $A_n^1 + A_n^2 + \cdots + A_n^k$, mỗi nút thử $n$ giá trị. Với $n = 7$ chỉ vài chục nghìn phép toán.

Kết quả chạy thật: C++: đúng 21/21 test, test chậm nhất chạy 0.004 giây. Bản Python: Python: đúng 21/21 test, test chậm nhất chạy 0.026 giây.

Ghi chú của mình: lời giải quay lui + used[] đạt 21/21 test trên bộ test của CLUE OJ (cả C++ lẫn Python). Các bạn nhớ khuôn "đánh dấu → gọi đệ quy → bỏ đánh dấu" này, nó sẽ quay lại trong rất nhiều bài: hoán vị, n quân hậu, tô màu đồ thị...

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 😇