Tìm hoán vị nhỏ nhất của số cho trước trong C++

Trong bài toán này, cho một số lớn N. Nhiệm vụ là tìm hoán vị nhỏ nhất của số đó.

Ví dụ minh họa:

Đầu vào

N = 4529016

Đầu ra

1024569

Phương pháp giải

Giải pháp đơn giản: lưu số nguyên lớn vào chuỗi. Sắp xếp chuỗi là kết quả. Nếu có số 0 dẫn đầu, dịch chúng về sau chữ số đầu tiên khác 0.

Chương trình minh họa:

Ví dụ

#include <bits/stdc++.h> 
using namespace std; 

string smallestNumPer(string s) { 
    int len = s.length(); 
    sort(s.begin(), s.end()); 
    int i = 0; 
    while (s[i] == '0') 
        i++; 
    swap(s[0], s[i]); 
    return s; 
} 

int main() { 
    string s = "4529016"; 
    cout<<"The number is "<<s<<endl; 
    cout<<"The smallest permutation of the number is "<<smallestNumPer(s); 
    return 0; 
}

Kết quả

The number is 4529016 The smallest permutation of the number is 1024569