Hướng dẫn hoán vị c++

Code c:

#include

int Hoanvi(int a, int b);

int main() {

                                             int a, b;

                                             do {

                                                printf("Nhap a = ");

                                                scanf("%d",&a);

                                                printf("Nhap b = ");

                                                scanf("%d",&b);

                                             } while(a<0 || b<0);

                                             Hoanvi(a,b);

}

int Hoanvi(int a, int b) {

                                             int temp;

                                             temp=a;

                                             a=b;

                                             b=temp;

                                             printf("a = %d, b = %d",a,b);

}

$\color{#ff7500}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}$ $\color{#ff7500}{\text{Và sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu với thuật của mình và thu được bài học cho mình}}$ $\color{#ff7500}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}$ [ở đây](https://www.facebook.com/SPectiar2k/)

\color{orange}{\text{Mục lục}}

\color{#300000}{\text{1. Hướng dẫn}}

• \color{#903030}{\text{}} Thử từng hoán vị và trong các hoán vị lớn hơn ta chọn cái nhỏ nhất

\color{#c01515}{\text{1. Tiếp cận}}

• \color{#f03030}{\text{}} Xét số X như là một xâu các chữ số S.

Ta sắp xếp S thành số nhỏ nhất (dãy tăng dần) T có thể và liên tục chọn hoán vị tiếp theo của T cho tới khi T > S thì xuất T

Trong C++ có 2 hàm là next_permutation (tìm hoán vị tiếp theo) prev_permutation (tìm hoán vị trước đó) có thể chạy trong O(n!) khi duyệt tất cả hoán vị

Nếu T không còn hoán vị nào nữa hay S là số lớn nhất (dãy giảm dần) thì xuất 0

int main()
{
    string s;
    cin >> s;

    string t = s;
    sort(all(t));
    while (t <= s) if (!next_permutation(all(t))) break;
    if (t > s) cout << t;
    else       cout << 0;
    return 0;
}

\color{#300000}{\text{2. Hướng dẫn}}

• \color{#903030}{\text{}} xây dưng từng chữ số cho S tới khi nào S \geq X thì dừng (S tạo ra từ tập các chữ số của X)

Xét vị trí [i] mà mình xây được S[i] > X[i] thì mình thêm bao nhiêu số đằng sau S > X luôn thỏa nên ta đưa S nối với phần còn lại được sắp xếp nhỏ nhất (tăng dần) thì ta sẽ được một số S nhỏ nhất lớn hơn X

• \color{#903030}{\text{}} Nếu S = X ta tìm hoán vị tiếp theo của S. Nếu vẫn S \leq X thì xuất 0, ngược lại xuất S

\color{#c01515}{\text{2. Tiếp cận}}

• \color{#f03030}{\text{}} Gọi fre[d] là số lần xuất hiện của chữ số d trong X

Mỗi lần thêm số d mình giảm fre[d]. Mỗi lần gọi đệ quy mà kết quả false thì tăng lại fre[d] là không tồn tại cách thỏa mãn, ngược lại kết quả true là tìm được dãy thỏa mãn và return true luôn.

Nếu ta xây được toàn bộ chữ số, ta return true

Nếu như khi xây tới ô thứ [i] mà không có X[i] nào để xây thêm, hay fre[X[i]] = 0. Ta sẽ tìm một số d > X[i] để thêm vào.

Nếu tồn tại d > X[i], ta sẽ thêm d vào sau S rồi thêm lần lượt các X[t] số t vào S với t = 0 \rightarrow 9. Sau đó return true

Nếu không tồn tại d > X[i] thì ta return false vì chỉ thêm được d < X[i] \Leftrightarrow S < X

Trong phần code, vì mình đang xây dần số S với độ dài lúc này là len thì phần tử tiếp theo mình thêm vào ở vị trí [len]

• \color{#903030}{\text{}}

Nếu S = X thì tìm hoán vị tiếp theo của S

Nếu sau đó S \leq X thì xuất 0

Nếu sau đó S > X thì xuất từng chữ số của S

• \color{#903030}{\text{}} O(n + alphabet)

Vì mình chỉ có lựa chọn là thêm hoặc không thêm s[i] (hay trong code là v[len]) nên O(n)

Và trong vòng lặp mình nối thêm chữ số cho S khi tìm được (d) thỏa mãn, thì các vòng lặp không lồng nhau nên O(n + alphabet) để nối các số t vào