Sinh kế tiếp
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Hàm tự tạo và đệ quy
- Chủ đề
- sinh kế tiếpvét cạn
- Trạng thái
Kiến thức cơ bản
Vì sao cần sinh kế tiếp
Có những bài mà em chưa biết cách tính thẳng ra đáp án, nhưng số khả năng cần thử lại không quá nhiều. Khi đó, ta thử hết mọi khả năng (gọi là vét cạn) và giữ lại khả năng tốt nhất. Cái khó là thử sao cho không sót và không lặp. Cách làm gọn nhất: xếp các khả năng theo một thứ tự cố định rồi từ khả năng hiện tại tìm ra khả năng đứng ngay sau nó. Việc đó gọi là sinh kế tiếp.
Hãy nghĩ đến công tơ mét của xe máy: mỗi lần chạy thêm 1 km, các chữ số cuối quay lên một nấc, và khi chữ số đạt 9 thì quay về 0 rồi “nhớ” sang chữ số bên trái. Tuần này, ta làm “công tơ mét” cho ba loại cấu hình: dãy nhị phân, tổ hợp, hoán vị. Các đoạn code là phần thân hàm main.
Mẫu 1: Dãy nhị phân kế tiếp
Dãy nhị phân độ dài n gồm n số, mỗi số là 0 hoặc 1. Có 2^n dãy khác nhau. Theo thứ tự từ điển, dãy đầu tiên là 00...0 và dãy cuối cùng là 11...1. Muốn tìm dãy kế tiếp ta làm như cộng thêm 1: từ phải sang trái, các số 1 đổi thành 0 (nhớ sang trái) cho đến khi gặp số 0 đầu tiên, rồi đổi số 0 đó thành 1.
0 1 1 1 (7) các số 1 cuối đổi thành 0: 0 0 0 0
số 0 đầu tiên (từ phải) đổi thành 1: 1 0 0 0 (8)
Mỗi dãy chỉ cần xử lý khoảng n bước.
vector<int> a(n, 0); // dãy đầu tiên: 00...0
while (true) {
for (int x : a) cout << x;
cout << "\n";
int i = n - 1;
while (i >= 0 && a[i] == 1) { // các số 1 ở cuối "nhớ" sang trái: đổi thành 0
a[i] = 0;
i--;
}
if (i < 0) break; // dãy 11...1 là dãy cuối cùng
a[i] = 1; // số 0 đầu tiên (từ phải) đổi thành 1
}
Dãy nhị phân còn có tác dụng khác: nếu có n phần tử, em quy ước phần tử i được chọn khi a[i] = 1, thì mỗi dãy nhị phân chính là một tập con. Duyệt hết 2^n dãy tức là duyệt hết mọi tập con. Ví dụ, để đếm số tập con có tổng đúng bằng S (khi n khoảng 20):
int dem = 0;
vector<int> mask(n, 0); // mask[i] = 1 nghĩa là chọn phần tử i
while (true) {
long long tong = 0;
for (int i = 0; i < n; i++) if (mask[i] == 1) tong += a[i];
if (tong == S) dem++;
int i = n - 1;
while (i >= 0 && mask[i] == 1) { mask[i] = 0; i--; }
if (i < 0) break;
mask[i] = 1;
}
cout << dem;
Mẫu 2: Tổ hợp kế tiếp
Tổ hợp chập k của n là cách chọn k số khác nhau từ 1, 2, ..., n, trong đó thứ tự không quan trọng nên ta viết chúng tăng dần: a[0] < a[1] < ... < a[k-1]. Ví dụ n = 4, k = 2 có 6 tổ hợp, theo thứ tự từ điển: 1 2, 1 3, 1 4, 2 3, 2 4, 3 4. Số cuối cùng a[i] không thể vượt quá n - k + i + 1 (để còn đủ chỗ cho các số sau). Vì thế muốn tìm tổ hợp kế tiếp, ta tìm vị trí i ngoài cùng bên phải mà a[i] chưa đạt giá trị lớn nhất, tăng nó lên 1, và xếp các vị trí sau thành các số liên tiếp nhỏ nhất.
n = 5, k = 3 tổ hợp: 1 4 5
vị trí 2: a = 5 = tối đa (5) -> bỏ qua
vị trí 1: a = 4 = tối đa (4) -> bỏ qua
vị trí 0: a = 1 < tối đa (3) -> tăng thành 2
các vị trí sau: 3, 4 -> tổ hợp kế tiếp: 2 3 4
vector<int> a(k);
for (int i = 0; i < k; i++) a[i] = i + 1; // tổ hợp đầu tiên: 1 2 ... k
while (true) {
for (int x : a) cout << x << " ";
cout << "\n";
int i = k - 1;
while (i >= 0 && a[i] == n - k + i + 1) i--; // bỏ qua các vị trí đã đạt giá trị lớn nhất
if (i < 0) break; // hết tổ hợp
a[i]++; // tăng vị trí này lên 1
for (int j = i + 1; j < k; j++) a[j] = a[j - 1] + 1; // các vị trí sau xếp liên tiếp, nhỏ nhất
}
Mẫu 3: Hoán vị kế tiếp
Hoán vị của 1, 2, ..., n là cách xếp n số đó theo một thứ tự (mỗi số xuất hiện đúng một lần). Có n! hoán vị. Ví dụ n = 3 có 6 hoán vị theo thứ tự từ điển: 123, 132, 213, 231, 312, 321.
Muốn tìm hoán vị kế tiếp, em đứng ở cuối dãy và đi sang trái:
- Bước 1: tìm vị trí i ngoài cùng bên phải sao cho a[i] < a[i + 1]. Phần bên phải i đang giảm dần (đã “lớn nhất” có thể). Không tìm được nghĩa là dãy giảm dần, đã là hoán vị cuối.
- Bước 2: trong phần bên phải, chọn số nhỏ nhất vẫn lớn hơn a[i] (gọi là a[j]) rồi đổi chỗ a[i] với a[j].
- Bước 3: đảo ngược phần bên phải i để nó thành tăng dần (nhỏ nhất).
2 3 5 4 1
^ bước 1: i = 1 (a[1] = 3 < a[2] = 5), phần sau 5 4 1 giảm dần
2 4 5 3 1 bước 2: số nhỏ nhất > 3 bên phải là 4, đổi chỗ 3 và 4
2 4 1 3 5 bước 3: đảo ngược phần sau 5 3 1 thành 1 3 5
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = i + 1; // hoán vị đầu tiên: 1 2 ... n
while (true) {
for (int x : a) cout << x << " ";
cout << "\n";
int i = n - 2;
while (i >= 0 && a[i] > a[i + 1]) i--; // tìm a[i] < a[i + 1] ngoài cùng bên phải
if (i < 0) break; // dãy giảm dần: hoán vị cuối cùng
int j = n - 1;
while (a[j] < a[i]) j--; // số nhỏ nhất lớn hơn a[i] ở bên phải
swap(a[i], a[j]);
reverse(a.begin() + i + 1, a.end()); // đoạn bên phải xếp lại tăng dần
}
Mẹo thi đấu (không bắt buộc): next_permutation
C++ đã viết sẵn ba bước trên trong hàm next_permutation (thư viện <algorithm>). Dãy phải được xếp tăng dần từ đầu thì mới liệt kê được hết. Với dãy có số trùng, hàm tự bỏ các hoán vị lặp.
vector<int> a = {1, 2, 3}; // phải xếp tăng dần trước khi bắt đầu
do {
for (int x : a) cout << x << " ";
cout << "\n";
} while (next_permutation(a.begin(), a.end())); // còn hoán vị kế tiếp thì tiếp tục
Một số hàm hay dùng
| swap(x, y) | Đổi chỗ hai giá trị x và y. |
|---|---|
| reverse(first, last) | Đảo ngược thứ tự các phần tử trong đoạn từ first đến trước last. Ví dụ reverse(a.begin() + 2, a.end()) đảo từ phần tử thứ 2 đến hết. |
| sort(first, last) | Xếp đoạn từ first đến trước last theo thứ tự tăng dần. |
| next_permutation(first, last) | (Không bắt buộc) Biến đoạn thành hoán vị kế tiếp rồi trả về true; nếu đã là hoán vị cuối thì trả về false. |
| prev_permutation(first, last) | (Không bắt buộc) Biến đoạn thành hoán vị đứng ngay trước rồi trả về true; nếu đã là hoán vị đầu thì trả về false. |
Ước lượng trước khi vét cạn
Máy tính làm được khoảng 108 phép tính trong một giây. Số cấu hình tăng rất nhanh: với n = 20 thì 2^n khoảng 106 (vẫn ổn), nhưng n! lại ra 2,4 × 1018 (không thể). Vì vậy đề bài hoán vị thường chỉ cho n không quá 8 đến 10. Em nhìn giới hạn của n trong đề để biết có thể vét cạn hay không.
| Dấu hiệu trong đề | Cách làm | Số cấu hình (để ước lượng) |
|---|---|---|
| Liệt kê (hoặc thử) mọi dãy nhị phân độ dài n; mọi tập con | Sinh nhị phân kế tiếp | 2^n (n = 20 là khoảng 106) |
| Chọn k phần tử từ n phần tử, không quan tâm thứ tự | Sinh tổ hợp kế tiếp | C(n, k) (n = 20, k = 10 là 184756) |
| Xếp n phần tử theo thứ tự, thử mọi cách xếp | Sinh hoán vị kế tiếp | n! (n = 8 là 40320; n = 10 là 3628800) |
| Cho một cấu hình, tìm cấu hình đứng ngay sau nó | Một lần “sinh kế tiếp”, không cần liệt kê hết | Chỉ khoảng n bước |
Luyện tập
Bài 1. Công tơ mét nhị phân
Công tơ mét của xe Gấu Po chỉ hiển thị các chữ số 0 và 1 trên n ô. Mỗi km chạy thêm, công tơ mét tăng thêm 1 theo cách cộng nhị phân (không đổi số ô). Cho dãy hiện tại, hãy cho biết dãy sau khi chạy thêm 1 km. Nếu dãy đang là toàn số 1 thì xe hết đường và in LAST.
| Đầu vào | Một dòng duy nhất là xâu s gồm các ký tự 0 và 1, dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | Xâu kế tiếp có cùng độ dài, hoặc LAST nếu s gồm toàn số 1. | |
| Test | Input | Output |
| 1 | 0111 | 1000 |
| 2 | 1111 | LAST |
| 3 | 1010 | 1011 |
Bài 2. Mọi dãy đèn
Hổ có n bóng đèn xếp thành hàng, mỗi bóng sáng (1) hoặc tắt (0). Hổ muốn liệt kê mọi cách bật tắt các bóng, theo thứ tự từ điển.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 10). | |
|---|---|---|
| Đầu ra | 2^n dòng, mỗi dòng một dãy n ký tự 0 hoặc 1 viết liền nhau, theo thứ tự tăng dần. | |
| Test | Input | Output |
| 1 | 2 | 00 01 10 11 |
| 2 | 1 | 0 1 |
Bài 3. Chọn bạn đi trực nhật
Lớp có n bạn đánh số từ 1 đến n. Cô giáo cần chọn đúng k bạn đi trực nhật. Hãy liệt kê mọi cách chọn, mỗi cách là các số thứ tự viết tăng dần, và các cách xếp theo thứ tự từ điển.
| Đầu vào | Một dòng gồm hai số nguyên n, k (1 ≤ k ≤ n ≤ 10). | |
|---|---|---|
| Đầu ra | Mỗi dòng là một cách chọn gồm k số tăng dần, cách nhau một dấu cách. Các dòng xếp theo thứ tự từ điển. | |
| Test | Input | Output |
| 1 | 4 2 | 1 2 1 3 1 4 2 3 2 4 3 4 |
| 2 | 3 3 | 1 2 3 |
Bài 4. Tổ hợp kế tiếp
Thỏ đã chọn k trong n bạn và viết số thứ tự của họ theo thứ tự tăng dần. Hãy cho biết cách chọn đứng ngay sau cách chọn của Thỏ theo thứ tự từ điển. Nếu cách chọn của Thỏ đã là cách cuối cùng thì in LAST.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: k số nguyên tăng dần, mỗi số từ 1 đến n. | |
|---|---|---|
| Đầu ra | k số của tổ hợp kế tiếp cách nhau một dấu cách, hoặc LAST. | |
| Test | Input | Output |
| 1 | 5 3 1 4 5 | 2 3 4 |
| 2 | 5 3 3 4 5 | LAST |
Bài 5. Hoán vị kế tiếp
Gấu Po xếp n thẻ bài đánh số từ 1 đến n thành một hàng, tạo ra một hoán vị. Hãy cho biết cách xếp đứng ngay sau cách xếp của Gấu Po theo thứ tự từ điển. Nếu đã là cách xếp cuối cùng thì in LAST.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên, là một hoán vị của 1, 2, ..., n. | |
|---|---|---|
| Đầu ra | Hoán vị kế tiếp, các số cách nhau một dấu cách, hoặc LAST. | |
| Test | Input | Output |
| 1 | 5 2 3 5 4 1 | 2 4 1 3 5 |
| 2 | 3 3 2 1 | LAST |
Bài 6. Mọi cách xếp hàng
Có n bạn đánh số từ 1 đến n xếp thành một hàng. Hãy liệt kê mọi cách xếp hàng theo thứ tự từ điển.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 8). | |
|---|---|---|
| Đầu ra | n! dòng, mỗi dòng là một cách xếp gồm n số cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 3 | 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 |
| 2 | 1 | 1 |
Bài 7. Hộp quà tổng S
Thỏ có n món quà, món thứ i có giá a[i]. Thỏ muốn chọn một số món (ít nhất một món) sao cho tổng giá đúng bằng S. Hỏi có bao nhiêu cách chọn? Hai cách chọn khác nhau nếu khác tập món quà được chọn.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 18; 1 ≤ S ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 108). | |
|---|---|---|
| Đầu ra | Số cách chọn. | |
| Test | Input | Output |
| 1 | 4 5 1 2 3 4 | 2 |
| 2 | 3 10 1 2 3 | 0 |
| 3 | 4 3 1 1 1 2 | 4 |
Bài 8. Từ đảo chữ
Hổ có một bịch chữ cái nhựa ghi bởi xâu s (có thể có chữ cái lặp lại). Hổ xếp các chữ cái này thành mọi từ khác nhau có thể. Hãy liệt kê tất cả các từ đó theo thứ tự bảng chữ cái.
| Đầu vào | Một dòng duy nhất là xâu s gồm chữ cái thường, dài từ 1 đến 8 ký tự. | |
|---|---|---|
| Đầu ra | Mỗi dòng một từ, theo thứ tự từ điển, không có từ nào bị lặp. | |
| Test | Input | Output |
| 1 | aab | aab aba baa |
| 2 | abc | abc acb bac bca cab cba |
Bài 9. Chỗ ngồi không kề nhau
Gấu Po có n bạn đánh số từ 1 đến n, cần xếp ngồi thành một hàng ngang. Có m cặp bạn hay cãi nhau nên không được ngồi kề nhau. Hỏi có bao nhiêu cách xếp chỗ thỏa mãn?
| Đầu vào | Dòng 1: hai số nguyên n, m (2 ≤ n ≤ 8; 0 ≤ m ≤ 10). m dòng sau, mỗi dòng gồm hai số nguyên u, v (1 ≤ u < v ≤ n) là một cặp không được ngồi kề nhau. | |
|---|---|---|
| Đầu ra | Số cách xếp chỗ thỏa mãn. | |
| Test | Input | Output |
| 1 | 3 1 1 2 | 2 |
| 2 | 4 0 | 24 |
Bài tập tự luyện
Bài 1. Dãy đèn sáng đúng k
Hổ có n bóng đèn xếp hàng. Hổ muốn bật đúng k bóng. Hãy liệt kê mọi cách bật, mỗi cách là một dãy gồm n ký tự 1 (sáng) hoặc 0 (tắt), theo thứ tự từ điển.
| Đầu vào | Một dòng gồm hai số nguyên n, k (1 ≤ n ≤ 12; 0 ≤ k ≤ n). | |
|---|---|---|
| Đầu ra | Mỗi dòng một dãy n ký tự viết liền nhau, theo thứ tự tăng dần. | |
| Test | Input | Output |
| 1 | 4 2 | 0011 0101 0110 1001 1010 1100 |
| 2 | 3 0 | 000 |
Bài 2. Hoán vị đứng ngay trước
Thỏ xếp n thẻ bài đánh số từ 1 đến n thành một hàng. Hãy cho biết cách xếp đứng ngay trước cách xếp của Thỏ theo thứ tự từ điển. Nếu đã là cách xếp đầu tiên thì in FIRST.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên, là một hoán vị của 1, 2, ..., n. | |
|---|---|---|
| Đầu ra | Hoán vị đứng ngay trước, các số cách nhau một dấu cách, hoặc FIRST. | |
| Test | Input | Output |
| 1 | 3 1 3 2 | 1 2 3 |
| 2 | 3 1 2 3 | FIRST |
Bài 3. Quà chia hết
Gấu Po có n món quà, món thứ i có giá a[i]. Gấu Po muốn chọn ít nhất một món sao cho tổng giá chia hết cho m. Hỏi có bao nhiêu cách chọn? Hai cách chọn khác nhau nếu khác tập món quà được chọn.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 18; 1 ≤ m ≤ 1000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách chọn. | |
| Test | Input | Output |
| 1 | 3 3 1 2 3 | 3 |
| 2 | 2 5 1 2 | 0 |
Bài 4. Chọn đội hình
Hổ có n cầu thủ, cầu thủ thứ i có sức mạnh a[i]. Hổ muốn chọn đúng k cầu thủ lập thành một đội sao cho tổng sức mạnh không nhỏ hơn L. Hỏi có bao nhiêu cách chọn đội? Hai đội khác nhau nếu khác tập cầu thủ.
| Đầu vào | Dòng 1: ba số nguyên n, k, L (1 ≤ k ≤ n ≤ 20; 1 ≤ L ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Số cách chọn đội. | |
| Test | Input | Output |
| 1 | 4 2 5 1 2 3 4 | 4 |
| 2 | 3 3 7 1 2 3 | 0 |
Bài 5. Trả nhầm mũ
Có n bạn, mỗi bạn có một chiếc mũ riêng đánh số trùng với số của bạn đó. Cô giáo trả mũ về lung tung, mỗi bạn nhận đúng một chiếc mũ. Hỏi có bao nhiêu cách trả mũ sao cho không bạn nào nhận đúng mũ của mình?
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 9). | |
|---|---|---|
| Đầu ra | Số cách trả mũ. | |
| Test | Input | Output |
| 1 | 3 | 2 |
| 2 | 4 | 9 |
Bài 6. Ổ khóa nhiều số
Ổ khóa của Thỏ có n bánh xe, mỗi bánh xe có các chữ số từ 0 đến m - 1. Hãy liệt kê mọi mã khóa có thể, theo thứ tự từ điển (mã đầu tiên toàn số 0).
| Đầu vào | Một dòng gồm hai số nguyên n, m (1 ≤ n ≤ 8; 1 ≤ m ≤ 9; m^n ≤ 5000). | |
|---|---|---|
| Đầu ra | Mỗi dòng một mã gồm n chữ số viết liền nhau, theo thứ tự tăng dần. | |
| Test | Input | Output |
| 1 | 2 3 | 00 01 02 10 11 12 20 21 22 |
| 2 | 3 2 | 000 001 010 011 100 101 110 111 |
Bài 7. Bước đi kế tiếp k lần
Gấu Po có một hoán vị của 1, 2, ..., n. Gấu Po lặp lại k lần thao tác “chuyển sang hoán vị kế tiếp”. Nếu ở một lần nào đó đã là hoán vị cuối cùng (không còn hoán vị kế tiếp) thì dừng và in LAST. Hãy cho biết kết quả cuối cùng.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 9; 1 ≤ k ≤ 400000). Dòng 2: n số nguyên, là một hoán vị của 1, 2, ..., n. | |
|---|---|---|
| Đầu ra | Hoán vị sau k lần chuyển (các số cách nhau một dấu cách), hoặc LAST nếu không đủ k lần. | |
| Test | Input | Output |
| 1 | 3 2 1 2 3 | 2 1 3 |
| 2 | 3 6 1 2 3 | LAST |
Bài 8. Phân công công việc
Thỏ có n bạn và n công việc. Nếu bạn i làm công việc j thì tốn c[i][j] phút. Mỗi bạn nhận đúng một việc, mỗi việc chỉ do một bạn làm. Hỏi tổng số phút ít nhất?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 8). n dòng tiếp theo, mỗi dòng gồm n số nguyên c[i][j] (1 ≤ c[i][j] ≤ 1000). | |
|---|---|---|
| Đầu ra | Tổng số phút ít nhất. | |
| Test | Input | Output |
| 1 | 3 9 2 7 6 4 3 5 8 1 | 9 |
| 2 | 1 5 | 5 |
Bài 9. Thử thách (không bắt buộc): Hoán vị thứ k
Các hoán vị của 1, 2, ..., n được xếp theo thứ tự từ điển và đánh số từ 1 (hoán vị 1 2 ... n là thứ 1). Hãy tìm hoán vị thứ k. (Gợi ý: có (n - 1)! hoán vị bắt đầu bằng mỗi số, hãy dùng điều đó để chọn dần từng số.)
| Đầu vào | Một dòng gồm hai số nguyên n, k (1 ≤ n ≤ 12; 1 ≤ k ≤ n!). | |
|---|---|---|
| Đầu ra | Hoán vị thứ k, các số cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 3 4 | 2 3 1 |
| 2 | 4 24 | 4 3 2 1 |
| 3 | 4 1 | 1 2 3 4 |
-
Gợi ý chung: Trước khi vét cạn, hãy ước lượng số cấu hình: 2^n với dãy nhị phân, C(n, k) với tổ hợp, n! với hoán vị. Con số quá lớn (nhiều hơn khoảng 108) thì không thể liệt kê hết. Khi gặp đề chỉ hỏi cấu hình kế tiếp của một cấu hình đã cho, chỉ cần sinh một lần, không cần liệt kê tất cả.
-
Lưu ý thêm: Trong sinh tổ hợp và hoán vị, hãy luôn kiểm tra điều kiện dừng (i < 0) trước khi dùng a[i]. Khi chỉ số chạy về -1 mà vẫn dùng a[i] thì chương trình lỗi. Với dãy nhị phân, nhớ in cấu hình hiện tại trước, rồi mới sinh cấu hình kế tiếp.