Lexicographical order

1. Initialize a list of strings and add numbers from 1 to N in it.
2. Now, all we need to do is sort the list and return it

In this approach, we will use recursion to generate all integers from 1 to N in a lexicographically ascending order. We will first initialize an empty list to store the integers. Now we will first fix the first digit of the numbers and then call recursion to generate the next possible digits. So, we will call our recursive function nine times for i = 1 to 9(possible digits for the leftmost most digit in any of the integers from 1 to N. The recursive algorithm is explained below.

Algorithm: 

N denotes the given integer.

CUR denotes the current number generated till now using recursion.

The list denotes the output list to return which will contain the integers from 1 to N in lexicographically sorted order.

void function(N, CUR, LIST):

1. If ‘CUR’ is less than N, then add ‘CUR’ to the list.
2. For i = 0 to 9, iterating all possible digits for the next place.
   1. CUR = CUR * 10 + i
   2. Recursively call to generate the next possible digits (if any), function(N, CUR, LIST).

Let us understand it by an example

Let N = 23, the recursion calls for this example are shown below:-

Similarly, we will call 3, 4, .. and 9 and generate all possible numbers.

1. Initialise the CURRENT element with 1.
2. Insert the CURRENT element to array A.
3. Update CURRENT with the trailing zeroes and add it into the output array A until it becomes greater than N which is the given input.
4. Note:  The lexicographically sorted numbers that will follow the number with trailing zeroes will be all the numbers with the same prefix except the last digit. Thus, keep on adding 1 to the CURRENT element and inserting it in the output array A at the same time.
5. Once the last digit of the CURRENT element becomes 0, this means that another cycle of the prefix has been started, thus, keep on removing the trailing zeroes until you reach the prefix you need.
6. Continue this till the size of the array becomes N.

Let us understand it by an example

Let, N = 22, initialize CURRENT with 1, CURRENT = 1 and add it to the list, A= [1]

Keep adding trailing zeros to current until CURRENT <= N 

CURRENT = 10, A = [1, 10]

CURRENT = 100, we won’t add this to array A as it is greater than N. Going back to the previous current element i.e CURRENT= CURRENT/10. CURRENT =10

Note: The lexicographically sorted numbers that will follow 10 will be all the numbers greater than 10 having the same prefix i.e we need to change only the last digit. For example:

1. If the CURRENT would have been 100, the next number would be 101 (CURRENT+1).
2. If CURRENTould has been 20, the next number would be 21 (CURRENT +1).
3. If the CURRENT would have been 120, the next number would be 121 (CURRENT +1).

CURRENT = 11 (10+1), A= [1, 10, 11]

CURRENT = 12, A= [1, 10, 11, 12]

Similarly, adding 13, 14, 15, .. 19 and A= [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Now, CURRENT(19) + 1 =20 but the next lexicographically greater number after 19 is 2 rather than 20. It must be noted that earlier the prefix was ‘1’ and all the numbers with prefix ‘1’ that were less than N+1 have been added to A. The new prefix will be existing CURRENT without trailing zeroes. 

For example: 

1. If CURRENT would have been 200 (199 +1), it means all the numbers with ‘19’as well as ‘1’ as prefix are added into the array. The new prefix will be ‘2’ which can be obtained by removing the trailing zeroes.
2. If CURRENT would have been 130 (129 +1), it means all the numbers with ‘12’ as prefix are added into the array. It should be noted that numbers with ‘1’ as prefix like ‘131, 132, 140 are still to be added. Thus, the new prefix will be ‘13’ which can be obtained by removing the trailing zeroes.

Now, CURRENT = 2, A= [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2]

Adding trailing zeroes and repeating steps as done for 1.

CURRENT = 20, A= [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20]

Adding all numbers with prefix 2 but less than 23 one by one will give

A= [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22]