Tìm số lớn hơn tiếp theo với cùng tập chữ số trong C++

Giới thiệu

Cho số N (dạng chuỗi). Tìm số nhỏ nhất lớn hơn N sử dụng chính xác các chữ số của N.

Ví dụ minh họa

Đầu vào

N = "92534"

Đầu ra

92543

Phương pháp giải

Thuật toán next permutation:

1. Duyệt từ phải sang trái, tìm i sao cho num[i] > num[i-1].
2. Nếu không tìm thấy → không có số lớn hơn.
3. Tìm chỉ số smallest trong [i, n-1] sao cho num[smallest] > num[i-1] và nhỏ nhất.
4. Hoán đổi num[i-1] và num[smallest].
5. Sắp xếp tăng dần phần tử từ i đến cuối.

Chương trình minh họa

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

void findNextGreater(char number[], int n) {
    int i, j;
    for (i = n-1; i > 0; i--)
        if (number[i] > number[i-1]) break;
    
    if (i == 0) {
        cout << "Next number is not possible";
        return;
    }
    
    int x = number[i-1], smallest = i;
    for (j = i+1; j < n; j++)
        if (number[j] > x && number[j] < number[smallest])
            smallest = j;
    
    swap(number[smallest], number[i-1]);
    sort(number + i, number + n);
    cout << number;
}

int main() {
    char number[] = "92534";
    int n = strlen(number);
    cout << "The next number with same set of digits is ";
    findNextGreater(number, n);
    return 0;
}

Đầu ra

The next number with same set of digits is 92543