Ordonare lexicografică pentru numere

Introducere

Problema #divimax cere, printre altele, determinarea celui mai mare număr care poate fi obținut prin concatenarea unor numere cunoscute.

De exemplu, pentru 15 234 1024, rexultatul va fi 234151024. La prima vedere, trebuie să sortăm numerele în ordine lexicografică inversă. Într-adevăr, ordonând numerele lexicografic invers, obținem 234 15 1024, iar prin concatenare obținem rezultatul de mai sus.

Dacă însă numere sunt 441 24 4, ordinea lexicografică (inversă) este 441 4 24. Prin concatenare obținem 441424, dar luându-le în ordinea 4 441 24 obținem un număr mai mare, 444124. Problema apare și atunci când dorim să obținem cel mai mic număr care poate fi obținut prin concatenarea unor numere date – simpla ordonare lexicografică nu este suficientă.

Problema

Considerăm următoarea cerință: Se dau două numere naturale A și B. Să se stabilească ordinea celor două valori, atfel încât numărul obținut prin concatenare să fie mai mic. Pentru 1024 și 15, răspunsul este 1024 15, iar pentru 331 3, răspunsul este 331 3.

Algoritm

Procedăm astfel:

• considerăm numărul x, obținut prin concatenarea lui A cu B;
• considerăm numărul y, obținut prin concatenarea lui B cu A;
• dacă x < y, atunci ordinea dorită este A B;
• în caz contrar, ordinea este B A.

Secvențe C++

Următoarele funcții C++ verifică dacă pentru a obține prin concatenarea numerelor A și B un număr mai mic le păstrăm sau nu ordinea. Returnează true dacă ordinea este A B, respectiv false dacă ordinea este B A. Ele pot fi folosite pentru a sorta un tablou folosind funcția STL sort().

Prima variantă construiește cele două numere descrise mai sus și le compară. Valorile lui A și B trebuie să fie suficient de mici încât să le putem concatena fără overflow!

bool Compare(int A , int B){
    int pA = 1, pB = 1, x = A, y = B;
    do pA *= 10, x /= 10; while(x);
    do pB *= 10, y /= 10; while(y);
    return 1LL * A * pB + B < 1LL * B * pA + A;
}

Următoarea secvență folosește funcția std::to_string(), construiește două stringuri și le verifică ordinea (lexicografică). Din păcate este lentă!

bool Compare(int A , int B){
    return to_string(A) + to_string(B) < to_string(B) + to_string(A);
}

Următoarea secvență construiește două tablouri cu cifrele celor două numere obținute prin concatenare și compară lexicografic tablourile.

bool Compare(int A , int B){
    int v[30], u[30];
    v[0] = u[0] = 0;
    while(A)
        v[++v[0]] = A % 10, A /= 10;
    while(B)
        u[++u[0]] = B % 10, B /= 10;
    std::reverse(v + 1, v + v[0] + 1);
    std::reverse(u + 1, u + u[0] + 1);
    int lgv = v[0] , lgu = u[0];
    for(int i = 1 ; i <= lgu; i ++)
        v[++v[0]] = u[i];
    for(int i = 1 ; i <= lgv; i ++)
        u[++u[0]] = v[i];
    //aici v[0] == u[0]
    for(int i = 1 ; i <= v[0] ; i ++)
         if(v[i] < u[i])
              return true;
         else
            if(v[i] > u[i])
                 return false;
    return false;
}

Observații:

• în secvența de mai sus, dimensiunile tablourilor v și u se memorează în V[0], resectiv u[0];
• reverse este o funcție STL, disponibilă în headerul algorithm, care oglindește tabloul
• utilizăm faptul că, prin construcția lor, cele două tablouri au aceeași lungime. În caz contar, algoritmul este incomplet!