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> s; string t = s; sort[all[t]]; while [t s] cout 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