Khóa học CTDL và GT

Bài 11.2. Sinh hoán vị

Chào mừng các bạn đã trở lại với series về Cấu trúc dữ liệu và Giải thuật (CTDL và GT)!

Trong thế giới lập trình và toán học, đôi khi chúng ta cần xem xét tất cả các cách có thể để sắp xếp một tập hợp các phần tử. Tưởng tượng bạn có một bộ ba quả bóng màu Đỏ, Xanh lá, Xanh dương. Bạn có thể sắp xếp chúng theo bao nhiêu cách khác nhau? Đỏ-XanhLá-XanhDương, Đỏ-XanhDương-XanhLá, ... Bài toán này chính là về hoán vị. Và trong bài viết này, chúng ta sẽ đi sâu vào cách sinh ra tất cả các hoán vị đó một cách có hệ thống.

Sinh hoán vị không chỉ là một bài toán lý thuyết trong tổ hợp. Nó có rất nhiều ứng dụng thực tế, từ việc tìm kiếm tất cả các tuyến đường có thể trong bài toán Người du lịch (Traveling Salesperson Problem), kiểm tra các khả năng trong mật mã học, đến việc tạo ra các bài kiểm tra tự động hoặc đơn giản là hiểu sâu hơn về sức mạnh của đệ quy và quay lui (backtracking) – những kỹ thuật cực kỳ quan trọng trong giải thuật.

Hãy cùng nhau "mổ xẻ" bài toán thú vị này!

Hoán vị là gì?

Trước hết, hãy định nghĩa rõ ràng. Hoán vị của một tập hợp gồm n phần tử phân biệt là một cách sắp xếp các phần tử đó theo một thứ tự nhất định.

Ví dụ, với tập hợp {1, 2, 3}, các hoán vị của nó là:

• {1, 2, 3}
• {1, 3, 2}
• {2, 1, 3}
• {2, 3, 1}
• {3, 1, 2}
• {3, 2, 1}

Có tổng cộng 6 hoán vị. Công thức tính số hoán vị của n phần tử phân biệt là n! (n giai thừa). Với n=3, số hoán vị là 3! = 3 2 1 = 6.

Bài toán đặt ra là làm sao để sinh ra và liệt kê tất cả n! hoán vị này một cách hiệu quả và không bỏ sót hay lặp lại bất kỳ hoán vị nào.

Phương pháp 1: Đệ quy và Quay lui (Backtracking)

Đây là một trong những cách tiếp cận phổ biến và trực quan nhất để sinh hoán vị. Ý tưởng chính là xây dựng hoán vị từng bước. Tại mỗi bước, chúng ta sẽ chọn một phần tử chưa được sử dụng và đặt nó vào vị trí hiện tại trong hoán vị đang xây dựng. Sau khi đặt một phần tử, chúng ta đệ quy để tiếp tục xây dựng phần còn lại của hoán vị. Khi hoàn thành một hoán vị (đã điền đủ n vị trí), chúng ta ghi nhận nó. Sau đó, điều quan trọng là quay lui (backtrack): chúng ta "tháo bỏ" lựa chọn vừa rồi và thử một lựa chọn khác cho vị trí hiện tại.

Hãy suy nghĩ về việc xây dựng hoán vị của {1, 2, 3}:

1. Vị trí 1:
   • Chọn 1. Hoán vị tạm thời: {1, ?, ?}. Đánh dấu 1 đã dùng.
   • Đệ quy: Sinh hoán vị cho {2, 3} vào vị trí 2, 3.
     • Vị trí 2:
       • Chọn 2 (chưa dùng). Hoán vị tạm thời: {1, 2, ?}. Đánh dấu 2 đã dùng.
       • Đệ quy: Sinh hoán vị cho {3} vào vị trí 3.
         • Vị trí 3:
           • Chọn 3 (chưa dùng). Hoán vị tạm thời: {1, 2, 3}. Đánh dấu 3 đã dùng.
           • Đã điền đủ 3 vị trí! Ghi nhận hoán vị {1, 2, 3}.
           • Quay lui: Bỏ đánh dấu 3.
         • Không còn lựa chọn nào khác cho vị trí 3.
       • Quay lui: Bỏ đánh dấu 2.
       • Chọn 3 (chưa dùng). Hoán vị tạm thời: {1, 3, ?}. Đánh dấu 3 đã dùng.
       • Đệ quy: Sinh hoán vị cho {2} vào vị trí 3.
         • Vị trí 3:
           • Chọn 2 (chưa dùng). Hoán vị tạm thời: {1, 3, 2}. Đánh dấu 2 đã dùng.
           • Đã điền đủ 3 vị trí! Ghi nhận hoán vị {1, 3, 2}.
           • Quay lui: Bỏ đánh dấu 2.
         • Không còn lựa chọn nào khác cho vị trí 3.
       • Quay lui: Bỏ đánh dấu 3.
     • Không còn lựa chọn nào khác cho vị trí 2.
   • Quay lui: Bỏ đánh dấu 1.
   • Chọn 2. Hoán vị tạm thời: {2, ?, ?}. Đánh dấu 2 đã dùng.
   • Đệ quy: Sinh hoán vị cho {1, 3} vào vị trí 2, 3.
     • ... (tiếp tục quá trình tương tự)
   • Quay lui: Bỏ đánh dấu 2.
   • Chọn 3. Hoán vị tạm thời: {3, ?, ?}. Đánh dấu 3 đã dùng.
   • Đệ quy: Sinh hoán vị cho {1, 2} vào vị trí 2, 3.
     • ... (tiếp tục quá trình tương tự)
   • Quay lui: Bỏ đánh dấu 3.

• Không còn lựa chọn nào khác cho vị trí 1.

Để quản lý việc "chọn" và "tháo bỏ" một cách hiệu quả trên cùng một cấu trúc dữ liệu (như một mảng hoặc vector), chúng ta có thể sử dụng kỹ thuật hoán đổi phần tử trực tiếp thay vì dùng mảng đánh dấu used.

Giả sử chúng ta đang sinh hoán vị cho mảng arr từ chỉ mục start đến hết.

• Base Case: Nếu start bằng kích thước mảng, tức là chúng ta đã cố định tất cả các phần tử từ đầu đến cuối, thì arr hiện tại chính là một hoán vị hoàn chỉnh.
• Recursive Step: Với vị trí hiện tại là start:
  • Chúng ta sẽ thử đặt từng phần tử từ vị trí start đến cuối mảng (arr[i], với i từ start đến n-1) vào vị trí start.
  • Để đặt arr[i] vào vị trí start, chúng ta hoán đổi (swap) arr[start] và arr[i].
  • Sau khi hoán đổi, phần tử ở vị trí start đã được cố định (tạm thời). Chúng ta đệ quy để sinh hoán vị cho phần còn lại của mảng, bắt đầu từ vị trí start + 1.
  • Sau khi lệnh đệ quy trả về (tức là đã sinh xong tất cả hoán vị có phần tử arr[i] ở vị trí start), chúng ta cần hoán đổi lại (swap back) arr[start] và arr[i]. Việc "hoán đổi lại" này chính là thao tác quay lui, đưa mảng về trạng thái trước khi thử lựa chọn arr[i], để chúng ta có thể thử lựa chọn phần tử khác (arr[i+1]) cho vị trí start.

Đây là sức mạnh và vẻ đẹp của backtracking kết hợp với hoán đổi tại chỗ!

Code C++ minh họa (Đệ quy + Hoán đổi)

#include <iostream>
#include <vector>
#include <algorithm> // Dùng cho std::swap

// Hàm đệ quy để sinh hoán vị
void generatePermutationsRecursive(std::vector<int>& arr, int start, int n) {
    // Base case: Nếu đã xét hết các phần tử (đến cuối mảng)
    if (start == n) {
        // Một hoán vị hoàn chỉnh đã được tạo ra
        for (int i = 0; i < n; ++i) {
            std::cout << arr[i] << (i == n - 1 ? "" : " ");
        }
        std::cout << std::endl;
        return; // Kết thúc nhánh đệ quy này
    }

    // Recursive step: Xét các phần tử từ start đến n-1
    // để đưa vào vị trí 'start'
    for (int i = start; i < n; ++i) {
        // 1. Chọn: Đưa phần tử arr[i] về vị trí start bằng cách hoán đổi
        std::swap(arr[start], arr[i]);

        // 2. Đệ quy: Sinh hoán vị cho phần còn lại của mảng (từ start + 1 đến n-1)
        generatePermutationsRecursive(arr, start + 1, n);

        // 3. Quay lui (Backtrack): Hoàn trả mảng về trạng thái trước khi hoán đổi
        // để có thể thử các lựa chọn khác cho vị trí 'start'
        std::swap(arr[start], arr[i]);
    }
}

int main() {
    std::vector<int> numbers = {1, 2, 3};
    int n = numbers.size();

    std::cout << "Cac hoan vi cua {1, 2, 3} (dung de quy + hoan doi):" << std::endl;
    generatePermutationsRecursive(numbers, 0, n);

    std::vector<char> letters = {'A', 'B', 'C', 'D'};
    n = letters.size();

    std::cout << "\nCac hoan vi cua {'A', 'B', 'C', 'D'} (dung de quy + hoan doi):" << std::endl;
    generatePermutationsRecursive(letters, 0, n); // Lưu ý: cần overload hoặc dùng template cho char

    // Để dùng lại hàm với char, bạn có thể viết lại hàm hoặc dùng template
    // Ví dụ đơn giản với char (viết lại hàm cho dễ hiểu trong bài blog):
    std::vector<char> letters2 = {'A', 'B', 'C', 'D'};
    int n2 = letters2.size();
    std::cout << "\nCac hoan vi cua {'A', 'B', 'C', 'D'} (dung de quy + hoan doi, cho char):" << std::endl;

    void generatePermutationsRecursiveChar(std::vector<char>& arr, int start, int n); // Khai báo trước

    generatePermutationsRecursiveChar(letters2, 0, n2);


    return 0;
}

// Định nghĩa lại hàm cho vector<char>
void generatePermutationsRecursiveChar(std::vector<char>& arr, int start, int n) {
    if (start == n) {
        for (int i = 0; i < n; ++i) {
            std::cout << arr[i] << (i == n - 1 ? "" : " ");
        }
        std::cout << std::endl;
        return;
    }

    for (int i = start; i < n; ++i) {
        std::swap(arr[start], arr[i]);
        generatePermutationsRecursiveChar(arr, start + 1, n);
        std::swap(arr[start], arr[i]); // Backtrack
    }
}

Giải thích Code:

1. generatePermutationsRecursive(std::vector<int>& arr, int start, int n): Đây là hàm đệ quy chính.
   • arr: Vector chứa các phần tử mà chúng ta muốn sinh hoán vị. Chúng ta truyền bằng tham chiếu (&) vì sẽ thay đổi trực tiếp trên vector này thông qua hoán đổi.
   • start: Chỉ mục (vị trí) hiện tại mà chúng ta đang cố định phần tử cho nó. Ban đầu gọi hàm này, start sẽ là 0.
   • n: Tổng số phần tử trong vector (arr.size()).
2. if (start == n): Đây là base case. Khi start đạt đến n, điều đó có nghĩa là chúng ta đã điền đầy đủ tất cả các vị trí từ 0 đến n-1. Mảng arr lúc này chính là một hoán vị hoàn chỉnh, và chúng ta in nó ra. Sau khi in, chúng ta return để kết thúc nhánh đệ quy hiện tại và quay trở lại bước trước đó.
3. for (int i = start; i < n; ++i): Vòng lặp này duyệt qua tất cả các phần tử từ vị trí start đến hết mảng. Mục đích là để thử từng phần tử trong số này làm phần tử tại vị trí start của hoán vị.
4. std::swap(arr[start], arr[i]);: Đây là bước Chọn. Chúng ta hoán đổi phần tử ở vị trí start với phần tử ở vị trí i. Sau hoán đổi này, phần tử ban đầu ở arr[i] (trước khi hoán đổi) đã được đưa về vị trí start. Vị trí start coi như đã được "cố định" tạm thời với giá trị này.
5. generatePermutationsRecursive(arr, start + 1, n);: Sau khi cố định arr[start], chúng ta Đệ quy gọi lại hàm chính để sinh hoán vị cho phần còn lại của mảng, bắt đầu từ vị trí start + 1.
6. std::swap(arr[start], arr[i]); // Backtrack: Đây là bước Quay lui. Sau khi lệnh đệ quy ở bước 5 hoàn thành (tức là tất cả các hoán vị có phần tử arr[start] hiện tại ở vị trí start đã được sinh ra và in ra), chúng ta cần hoàn tác lại phép hoán đổi ở bước 4. Việc hoán đổi lại này đưa mảng về trạng thái ban đầu trước khi chúng ta thử đặt arr[i] vào vị trí start. Điều này quan trọng để khi vòng lặp for tiếp tục sang giá trị i tiếp theo, chúng ta đang làm việc trên mảng gốc (hoặc mảng ở trạng thái của tầng đệ quy trên), không bị ảnh hưởng bởi các lựa chọn trước đó ở cùng mức đệ quy này.
7. main function: Khởi tạo một vector (numbers hoặc letters2), lấy kích thước n, và gọi hàm đệ quy ban đầu với start = 0.

Kỹ thuật đệ quy và quay lui này rất mạnh mẽ và có thể áp dụng cho nhiều bài toán tìm kiếm không gian trạng thái khác. Việc sử dụng hoán đổi tại chỗ giúp tiết kiệm bộ nhớ so với việc tạo ra các bản sao mảng mới ở mỗi bước.

Phương pháp 2: Sử dụng std::next_permutation trong C++ STL

Thư viện Standard Template Library (STL) của C++ cung cấp một hàm rất tiện lợi là std::next_permutation. Hàm này nhận vào một dãy (được định nghĩa bởi hai iterator) và biến đổi nó thành hoán vị kế tiếp theo thứ tự từ điển (lexicographical order). Nếu hoán vị hiện tại là hoán vị cuối cùng theo thứ tự từ điển, hàm sẽ trả về false, ngược lại trả về true.

Để sử dụng std::next_permutation để sinh tất cả hoán vị của một dãy, chúng ta cần làm như sau:

1. Sắp xếp dãy ban đầu theo thứ tự tăng dần. Đây sẽ là hoán vị đầu tiên (nhỏ nhất) theo thứ tự từ điển.
2. In ra hoán vị hiện tại.
3. Lặp đi lặp lại việc gọi std::next_permutation trên dãy.
4. Sau mỗi lần gọi thành công (hàm trả về true), chúng ta lại in ra hoán vị mới nhận được.
5. Dừng lại khi std::next_permutation trả về false.

Thuật toán đằng sau std::next_permutation dựa trên việc tìm kiếm sự thay đổi nhỏ nhất để tạo ra hoán vị kế tiếp theo thứ tự từ điển. Chi tiết thuật toán này khá phức tạp, nhưng ý tưởng là:

1. Tìm vị trí k lớn nhất sao cho arr[k] < arr[k+1]. Nếu không tìm thấy, đây là hoán vị cuối cùng.
2. Tìm vị trí l lớn nhất sao cho arr[k] < arr[l].
3. Hoán đổi arr[k] và arr[l].
4. Đảo ngược (reverse) dãy con từ vị trí k+1 đến hết.

Code C++ minh họa (std::next_permutation)

#include <iostream>
#include <vector>
#include <algorithm> // Dùng cho std::sort và std::next_permutation
#include <string>    // Dùng cho ví dụ với string (mảng char)

int main() {
    std::vector<int> numbers = {1, 2, 3};
    int n = numbers.size();

    // 1. Sắp xếp dãy ban đầu để có hoán vị đầu tiên
    std::sort(numbers.begin(), numbers.end());

    std::cout << "Cac hoan vi cua {1, 2, 3} (dung std::next_permutation):" << std::endl;

    // Lặp cho đến khi không còn hoán vị kế tiếp
    do {
        // In ra hoán vị hiện tại
        for (int i = 0; i < n; ++i) {
            std::cout << numbers[i] << (i == n - 1 ? "" : " ");
        }
        std::cout << std::endl;
    } while (std::next_permutation(numbers.begin(), numbers.end())); // Tạo và kiểm tra hoán vị kế tiếp

    std::cout << "\nCac hoan vi cua {'A', 'B', 'C'} (dung std::next_permutation tren string):" << std::endl;
    std::string s = "CAB"; // Thử với chuỗi không sắp xếp ban đầu
    std::sort(s.begin(), s.end()); // Phải sắp xếp trước!

    do {
        std::cout << s << std::endl;
    } while (std::next_permutation(s.begin(), s.end()));

     std::cout << "\nCac hoan vi cua {4, 1, 3, 2} (dung std::next_permutation):" << std::endl;
    std::vector<int> numbers2 = {4, 1, 3, 2};
    int n2 = numbers2.size();

    // Phải sắp xếp trước khi bắt đầu vòng lặp do-while
    std::sort(numbers2.begin(), numbers2.end());

    do {
        for (int i = 0; i < n2; ++i) {
            std::cout << numbers2[i] << (i == n2 - 1 ? "" : " ");
        }
        std::cout << std::endl;
    } while (std::next_permutation(numbers2.begin(), numbers2.end()));


    return 0;
}

Giải thích Code:

1. #include <algorithm>: Thư viện này chứa std::sort và std::next_permutation.
2. std::vector<int> numbers = {1, 2, 3};: Khởi tạo vector.
3. std::sort(numbers.begin(), numbers.end());: Rất quan trọng! Chúng ta cần sắp xếp vector để bắt đầu từ hoán vị nhỏ nhất theo thứ tự từ điển.
4. do { ... } while (std::next_permutation(numbers.begin(), numbers.end()));: Vòng lặp do-while là cấu trúc phù hợp.
   • Phần do { ... } được thực hiện ít nhất một lần. Ở lần đầu tiên, nó in ra hoán vị đã được sắp xếp (hoán vị ban đầu).
   • std::next_permutation(numbers.begin(), numbers.end()): Hàm này cố gắng biến đổi dãy từ numbers.begin() đến numbers.end() thành hoán vị kế tiếp theo thứ tự từ điển. Nếu thành công (tìm thấy hoán vị kế tiếp và thực hiện biến đổi), hàm trả về true. Nếu dãy hiện tại đã là hoán vị cuối cùng, hàm trả về false và dãy trở về trạng thái sắp xếp tăng dần (một đặc điểm của hàm khi không tìm thấy next permutation).
   • Vòng lặp while tiếp tục chừng nào std::next_permutation còn trả về true. Khi nó trả về false, vòng lặp kết thúc.
5. Phần code với std::string s = "CAB"; minh họa rằng std::next_permutation cũng hoạt động trên các container khác có iterator ngẫu nhiên như std::string, miễn là bạn cung cấp cặp iterator begin() và end() hợp lệ. Việc sắp xếp ban đầu vẫn cần thiết.
6. Ví dụ với numbers2 = {4, 1, 3, 2} cho thấy ngay cả khi mảng ban đầu không sắp xếp, việc gọi std::sort trước vòng lặp do-while là bắt buộc để std::next_permutation hoạt động đúng cách và sinh ra tất cả hoán vị theo thứ tự từ điển, bắt đầu từ hoán vị nhỏ nhất.

Phương pháp sử dụng std::next_permutation thường được ưu tiên trong thực tế vì nó ngắn gọn, hiệu quả cao (thường là cài đặt tối ưu), và ít bị lỗi hơn so với tự cài đặt đệ quy phức tạp. Tuy nhiên, việc hiểu cách cài đặt đệ quy và quay lui lại là cực kỳ quan trọng để nắm vững các kỹ thuật giải thuật cơ bản.

So sánh hai phương pháp

• Đệ quy + Hoán đổi (Backtracking):
  • Ưu điểm: Giúp hiểu sâu sắc về kỹ thuật đệ quy, quay lui và cách xây dựng lời giải từng bước. Rất hữu ích cho việc học CTDL&GT. Có thể dễ dàng tùy biến (ví dụ: sinh hoán vị con, hoán vị với điều kiện).
  • Nhược điểm: Cài đặt có thể phức tạp hơn một chút, dễ gặp lỗi backtracking nếu không cẩn thận. Sử dụng stack cho đệ quy, có thể gây stack overflow với n quá lớn (mặc dù n! tăng rất nhanh nên giới hạn về thời gian chạy thường đến trước giới hạn stack). Thứ tự sinh ra các hoán vị không đảm bảo theo từ điển (phụ thuộc vào thứ tự lặp trong vòng for).
• std::next_permutation:
  • Ưu điểm: Cực kỳ ngắn gọn, dễ sử dụng. Cài đặt hiệu quả, thường tối ưu về thời gian chạy cho việc sinh hoán vị kế tiếp. Đảm bảo sinh theo thứ tự từ điển. Là cách thực tế nhất khi bạn chỉ cần sinh tất cả hoán vị.
  • Nhược điểm: Như một "hộp đen", không giúp bạn hiểu sâu bên trong thuật toán sinh hoán vị kế tiếp. Cần sắp xếp dãy ban đầu.

Lời khuyên: Khi học, hãy tập trung vào việc hiểu và cài đặt được phương pháp đệ quy và quay lui. Khi làm bài tập hoặc dự án thực tế cần sinh hoán vị, hãy ưu tiên sử dụng std::next_permutation để tiết kiệm thời gian và đảm bảo tính đúng đắn.

Các biến thể

Bài toán sinh hoán vị cơ bản là với các phần tử phân biệt. Tuy nhiên, cũng có các biến thể phổ biến:

• Hoán vị với các phần tử lặp lại: Nếu tập hợp có các phần tử giống nhau (ví dụ: {1, 2, 2}), số lượng hoán vị sẽ ít hơn n!, và bạn cần điều chỉnh thuật toán để tránh sinh ra các hoán vị trùng lặp. Phương pháp đệ quy có thể được sửa đổi bằng cách chỉ cho phép chọn một phần tử nếu nó khác với phần tử vừa mới được thử ở cùng mức đệ quy, hoặc sử dụng một tập hợp (set) để lưu trữ các hoán vị đã sinh ra và loại bỏ trùng lặp (kém hiệu quả). std::next_permutation tự động xử lý các phần tử lặp lại một cách chính xác và sinh ra các hoán vị duy nhất theo thứ tự từ điển.
• K-hoán vị (Permutation of size K): Sinh ra tất cả các dãy con có thứ tự gồm K phần tử được chọn từ N phần tử (K <= N). Phương pháp đệ quy có thể dễ dàng mở rộng để giải quyết bài toán này bằng cách dừng lại khi độ dài của hoán vị tạm thời đạt K.

Bài tập ví dụ:

[DSA-ThuatToanSinh].Xâu nhị phân kế tiếp

Cho xâu nhị phân X[], nhiệm vụ của bạn là hãy đưa ra xâu nhị phân tiếp theo của X[]. Ví dụ X[] ="010101" thì xâu nhị phân tiếp theo của X[] là "010110".

Input Format

Dòng đầu tiên đưa vào số lượng test T. Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một xâu nhi phân X. T, X[] thỏa mãn ràng buộc: 1≤T≤100; 1≤length(X)≤10^3.

Constraints

.

Output Format

Đưa ra kết quả mỗi test theo từng dòng.

Ví dụ:

Dữ liệu vào

2
101010
111111

Dữ liệu ra

101011
000000

Chào bạn, đây là hướng dẫn giải bài toán "Xâu nhị phân kế tiếp" bằng C++ một cách ngắn gọn:

1. Ý tưởng chính: Bài toán này tương đương với việc cộng thêm 1 vào một số biểu diễn dưới dạng nhị phân.
2. Thực hiện: Duyệt xâu nhị phân từ phải sang trái.
3. Tìm vị trí thay đổi: Tìm ký tự '0' đầu tiên từ bên phải.
   • Nếu tìm thấy '0' tại chỉ số i: Đổi ký tự tại chỉ số i thành '1'. Tất cả các ký tự từ chỉ số i+1 đến cuối xâu (những ký tự ban đầu phải là '1' để ta duyệt qua chúng) đổi thành '0'. Đây chính là xâu nhị phân kế tiếp. Dừng quá trình duyệt.
   • Nếu không tìm thấy '0' nào (tức là xâu ban đầu toàn là '1'): Xâu kế tiếp là xâu có cùng độ dài nhưng toàn là '0'.
4. Xử lý nhiều test case: Đọc số lượng test case T, sau đó lặp lại quá trình trên T lần cho mỗi xâu nhị phân nhập vào.

Làm thêm nhiều bài tập miễn phí tại đây