Thuật toán liệt kê hoán vị theo thứ tự từ điển

Bài toán: Cho hoán vị (a_(1), a_(2), a...(n)), tìm hoán vị tiếp theo theo thứ tự từ điển.
Ví dụ: Hoán vị tiếp theo theo thứ tự từ điển của (0,1,2,5,3,3,0) là (0,1,3,0,2,3,5)

Thuật toán:
+ Chúng ta sẽ tìm hoán vị tiếp theo sao cho khoảng cách giữa hoán vị tiếp theo này và hoán vị ban đầu có “khoảng cách” là ngắn nhất. Cũng giống như việc tăng số đếm, chúng ta tăng dần độ lớn các số từ bên phải qua và giữ nguyên phần bên trái; việc liệt kê tttđ cũng tương tự: đầu tiên tìm vị trí i bên phải nhất mà tại đó a[i] < a[i+1] ( nhận thấy rằng từ a[i+1] đến a[n] là đoạn giảm dần, vì vậy không thể tăng thêm được nữa).
Ta có i = 3 vì a[3] = 2 a[i] sẽ được hoán đổi với vị trí j.
Ta có j = 6, vì a[6] = 3 > a[i] = a[3] = 2.
Hoán vị sau khi đổi chỗ i và j (0,1,3,5,3,2,0)

+ Sau khi đổi chỗ, đoạn từ a[i+1] đến a[n] vẫn đảm bảo tính chất giảm dần, nên chúng ta phải “lật ngược” đoạn này lại để nó là nhỏ nhất đối với vị trí i mới là a[i] = a[3] = 3
Hoán vị sau khi “lật ngược”: (0,1,3,0,2,3,5)

Code: Hàm sau trả về true nếu hoán vị được truyền vào chưa phải là hoán vị cuối cùng, false nếu ngược lại

bool hoanvi_tt(string & s) {
    
    for(int i = (int)s.size()-2; i >= 0; i--) {
        if (s[i] < s[i+1]) {
            for(int j = (int)s.size()-1; j > i; j--)
                if (s[i] < s[j]) {
                    swap(s[i], s[j]);
                    reverse(s.begin()+i+1,s.end());
                    return true;
                }
        }
    }
    
    return false;
}

Sử dụng STL của C++:

Trong stl của C++ có hàm next_permutation() ( hoán vị tiếp theo) hoàn toàn tương tự hàm hoanvi_tt ở trên. Có thể xem cách dùng tại cplusplus.com

Happy coding

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s