Given an integer N, print numbers from 1 to N in lexicographic order

Question

I'm trying to print the numbers from 1 to N in lexicographic order, but I get a failed output. for the following input 100, I get the 100, but its shifted and it doesn't match with the expected output, there is a bug in my code but I can not retrace it.

class Solution {
public:
    vector<int> lexicalOrder(int n) {
         vector<int> result;
        for(int i = 1; i <= 9; i ++){
        int j = 1;
        while( j <= n){
            for(int m = 0; m < j ; ++ m){
                if(m + j * i <= n){

                    result.push_back(m+j*i);
                }
            }
            j *= 10;
        }
    }
    return result;

    }
};



Input:
100
Output:
[1,10,11,12,13,14,15,16,17,18,19,100,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,50,51,52,53,54,55,56,57,58,59,6,60,61,62,63,64,65,66,67,68,69,7,70,71,72,73,74,75,76,77,78,79,8,80,81,82,83,84,85,86,87,88,89,9,90,91,92,93,94,95,96,97,98,99]

Expected:
[1,10,100,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47

Answer 1

As the numbers are unique from 1 to n, you can use a set of size n and insert all of them into it and then print them out. set will automatically keep them sorted in lexicographical order if you store the numbers as a string. Here is the code, short and simple:

 void lexicographicalOrder(int n){
     set<string> ans;
     for(int i = 1; i <= n; i++)
        ans.insert(to_string(i));
     for(auto ele : ans)
        cout <<ele <<"\n";
 } 

Answer 2

An easy one to implement is to convert numbers to string, them sort the array of strings with std::sort in algorithm header, that sorts strings in lexicographical order, then again turn numbers to integer

• Make a vector of integers you want to sort lexicographically, name it numbers.
• Make an other vector and populate it strings of numbers in the first vector. name it strs.
• Sort strs array.4. Convert strings of strs vector to integers and put it in vectors
  

List item

#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;


string int_to_string(int x){
    string ret;
    while(x > 0){
        ret.push_back('0' + x % 10);
        x /= 10;
    }
    reverse(ret.begin(), ret.end());
    return  ret;
}

int main(){
    vector<int> ints;
    ints.push_back(1);
    ints.push_back(2);
    ints.push_back(100);
    vector<string> strs;
    for(int i = 0; i < ints.size(); i++){
        strs.push_back(int_to_string((ints[i])));
    }
    sort(strs.begin(), strs.end());
    vector<int> sorted_ints;
    for(int i = 0; i < strs.size(); i++){
        sorted_ints.push_back(atoi(strs[i].c_str()));
    }
    for(int i = 0; i < sorted_ints.size(); i++){
        cout<<sorted_ints[i]<<endl;
    }
}

Answer 3

You are looping through all 2 digit numbers starting with 1 before outputting the first 3 digit number, so your approach won't work.

One way to do this is to output the digits in base 11, padded out with leading spaces to the maximum number of digits, in this case 3. Output 0 as a space, 1 as 0, 2 as 1 etc. Reject any numbers that have any non-trailing spaces in this representation, or are greater than n when interpreted as a base 10 number. It should be possible to jump past multiple rejects at once, but that's an unnecessary optimization. Keep a count of the numbers you have output and stop when it reaches n. This will give you a lexicographical ordering in base 10.

Example implementation that uses O(1) space, where you don't have to generate and sort all the numbers up front before you can output the first one:

void oneToNLexicographical(int n)
{
    if(n < 1) return;

    // count max digits
    int digits = 1, m = n, max_digit11 = 1, max_digit10 = 1;
    while(m >= 10)
    {
        m /= 10; digits++; max_digit11 *= 11; max_digit10 *= 10;
    }

    int count = 0;
    bool found_n = false;
    // count up starting from max_digit * 2 (first valid value with no leading spaces)
    for(int i = max_digit11 * 2; ; i++)
    {
        int val = 0, trailing_spaces = 0;
        int place_val11 = max_digit11, place_val10 = max_digit10;
        // bool valid_spaces = true;
        for(int d = 0; d < digits; d++)
        {
            int base11digit = (i / place_val11) % 11;
            if(base11digit == 0)
            {
                trailing_spaces++;
                val /= 10;
            }
            else
            {   
                // if we got a non-space after a space, it's invalid
                // if(trailing_spaces > 0)
                // {
                //  valid_spaces = false;
                //  break;  // trailing spaces only
                // }
                val += (base11digit - 1) * place_val10;
            }
            place_val11 /= 11;
            place_val10 /= 10;
        }
        // if(valid_spaces && (val <= n))
        {
            cout << val << ", ";
            count++;
        }
        if(val == n)
        {
            found_n = true;
            i += 10 - (i % 11); // skip to next number with one trailing space
        }

        // skip past invalid numbers:

        // if there are multiple trailing spaces then the next run of numbers will have spaces in the middle - invalid
        if(trailing_spaces > 1)
            i += (int)pow(11, trailing_spaces - 1) - 1;
        // if we have already output the max number, then all remaining numbers
        // with the max number of digits will be greater than n
        else if(found_n && (trailing_spaces == 1))
            i += 10;

        if(count == n)
            break;
    }
}

This skips past all invalid numbers, so it's not necessary to test valid_spaces before outputting each.

The inner loop can be removed by doing the base11 -> base 10 conversion using differences, making the algorithm O(N) - the inner while loop tends towards a constant:

int val = max_digit10;
for(int i = max_digit11 * 2; ; i++)
{
    int trailing_spaces = 0, pow11 = 1, pow10 = 1;
    int j = i;
    while((j % 11) == 0)
    {
        trailing_spaces++;
        pow11 *= 11;
        pow10 *= 10;
        j /= 11;
    }

    int output_val = val / pow10;       
    if(output_val <= n)
    {
        cout << output_val << ", ";
        count++;
    }
    if(output_val == n)
        found_n = true;

    if(trailing_spaces > 1)
    {
        i += (pow11 / 11) - 1;
    }
    else if(found_n && (trailing_spaces == 1))
    {
        i += 10;
        val += 10;
    }
    else if(trailing_spaces == 0)  
        val++;

    if(count == n)
        break;
}

Demonstration

The alternative, simpler approach is just to generate N strings from the numbers and sort them.

Answer 4

Maybe more general solution?

#include <vector>
#include <algorithm>

using namespace std;

// returns true is i1 < i2 according to lexical order
bool lexicalLess(int i1, int i2) 
{
    int base1 = 1;
    int base2 = 1;
    for (int c = i1/10; c > 0; c/=10) base1 *= 10;
    for (int c = i2/10; c > 0; c/=10) base2 *= 10;
    while (base1 > 0 && base2 > 0) {
        int d1 = i1 / base1;
        int d2 = i2 / base2;
        if (d1 != d2) return (d1 < d2);
        i1 %= base1;
        i2 %= base2;
        base1 /= 10;
        base2 /= 10;
    }
    return (base1 < base2);
}

vector<int> lexicalOrder(int n) {
    vector<int> result;
    for (int i = 1; i <= n; ++i) result.push_back(i);
    sort(result.begin(), result.end(), lexicalLess);
    return result;
}

The other idea for lexicalLess(...) is to convert integers to string before comparision:

#include <vector>
#include <algorithm>
#include <string>    
#include <boost/lexical_cast.hpp>

using namespace std;

// returns true is i1 < i2 according to lexical order
bool lexicalLess(int i1, int i2) 
{
    string s1 = boost::lexical_cast<string>(i1);
    string s2 = boost::lexical_cast<string>(i2);
    return (s1 , s2);
}

You need Boost to run the second version.

Answer 5

Think about when i=1,j=10 what will happen in

for(int m = 0; m < j ; ++ m){
                if(m + j * i <= n){

                    result.push_back(m+j*i);
                }
            }

Yes,result will push_back 10(0+10*1),11(1+10*1),12(2+10*1).. Here is a solution:

#include <iostream>
#include <vector>
#include <string>
std::vector<int> fun(int n)
{
        std::vector<std::string> result;
        for (int i = 1; i <= n; ++i) {
            result.push_back(std::to_string(i));
        }
        std::sort(result.begin(),result.end());
        std::vector<int> ret;
        for (auto i : result) {
            ret.push_back(std::stoi(i));
        }
        return ret;
}
int main(int argc, char *argv[])
{
        std::vector<int> result = fun(100);
        for (auto i : result) {
            std::cout << i << ",";
        }
        std::cout << std::endl;
        return 0;
}