Looking for all numbers where each digit is bigger than the previous digit

Question

This is the "Increasing Number problem", where we are looking for all numbers with \$n\$ digits where each digit is bigger than the digit before it. Or in Mathematical therms where:

$$\mathit{IncreasingNumber} = c_n \times 10^n + c_{n-1} \times 10^{n-1} + \cdots + c_1 * 10 + c_0$$

and \$c_i < c_{i-1}\$.

Examples: 123456789 or 123 or 569 or 139 or 45 or 12379. Goal: Give out all numbers that fullfill these properties depending on the number of digits \$n\$. This is my brute force code:

Sub AllIncreasingNumbers(N As Integer)
Dim Number As Long
Dim i As Long
Dim j As Integer
Dim lastdig As Integer
Dim remainder As Long
Dim thisdig As Integer



For i = (1 * 10 ^ (N - 1)) To 10 ^ (N)
    remainder = i
    lastdig = 0
    For j = (N - 1) To 0 Step -1
        thisdig = (remainder \ (10 ^ j))
        If Not (lastdig < thisdig) Then
        GoTo NotPass
        End If
        lastdig = thisdig
        remainder = remainder Mod (10 ^ j)
    Next j
    Debug.Print i
NotPass:
Next i
End Sub

If you haven't guessed it, it functions as following: go through all Numbers with N digits and check if they are increasing Numbers, if yes print them.

For \$n\$ = 2 to 6 it is reasonably fast but for \$n\$ = 8 or 9 it is really slow despite \$n=9\$ only having one solution 123456789. I think there could be a recursive algorithm to solve this but I can't figure it out. I used VBA because thats the language I am most familiar with but actually I am more intrested in the recursive algorithm to solve this. As soon as I have the algorithm I am able to implement it.

Answer 1

Instead of searching all numbers and checking them one by one, why not construct the numbers from the rule. In other words, start with the smallest digit being 1, then the next digit being 2 and so on. The digits can then be increased right to left as long as the rule holds.

For example, finding all 8 digit numbers:

Start with each digit increasing by 1 left to right:

• 12345678

Add one to the final digit:

• 12345679

Run out of digits so increase the digit to the left:

• 12345689
• 12345789
• 12346789
• ...
• 23456789

EDIT for further explanation:

For smaller numbers, you then need to repeat this process recursively. For example:

• 123 -> 124 -> 125 ... 129

You would now need to "reset" the second digit and any following it to one above what it was:

• 129 -> 134 -> 135 -> 136 ... 139

• 139 -> 145 -> 146 -> 147 ... 149

• 149 -> 156 -> 157 -> 158 -> 159

And so on.

You are still effectively working backwards through the digits, recursively increasing them right to left.

Hope that helps.

Answer 2

Here is idea: starting from the smallest number:

[[1] [2] [3] [4] [5] [6] [7] [8] [9]]

Every subarray holds number ending with the specific digits.

Then increasing one digit for each subarray.

[1] -> [12] [13] [14] [15] [16] [17] [18] [19] 
[2] -> [13] [14] [15] [16] [17] [18] [19]
[3] -> [14] [15] [16] [17] [18] [19]
[4] -> [15] [16] [17] [18] [19]
[5] -> [16] [17] [18] [19]
[6] -> [17] [18] [19]
[7] -> [18] [19]
[8] -> [19]

Then put every number into their bucket which ends with it. (if it's 9. then its the last number)

Here is the result:

  [[], [12], [13, 23], [14, 24, 34], [15, 25, 35, 45],
  [16, 26, 36, 46, 56], [17, 27, 37, 47, 57, 67], 
  [18, 28, 38, 48, 58, 68, 78], [19, 29, 39, 49, 59, 69, 79, 89]]

Then recursive or iterate till N == 9.

I prefer to use swift but the logic is same and obvious:

     var  base: [[Int]] = [[1],[2],[3],[4],[5],[6],[7],[8],[9]]

     var result : [Int] = []

     result.append(contentsOf: base.flatMap{$0})

     for N in 0..<8{

      var singleStep: [[Int]] = [[],[],[],[],[],[],[],[],[]]
          for i in N..<8 {
             for j in (i+1)..<9{
                for each in base[i]{
                    singleStep[j].append(each * 10 + j + 1)
                 }
                }
               }
       base = singleStep
       result.append(contentsOf: base.flatMap{$0})
       print(base)
      }
      print(result)

     [1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 23, 14, 24, 34, 15, 25, 35, 45, 16, 
      26, 36, 46, 56, 17, 27, 37, 47, 57, 67, 18, 28, 38, 48, 58, 68, 78, 19, 
      29, 39, 49, 59, 69, 79, 89, 123, 124, 134, 234, 125, 135, 235, 145, 245, 
      345, 126, 136, 236, 146, 246, 346, 156, 256, 356, 456, 127, 137, 237, 
      147, 247, 347, 157, 257, 357, 457, 167, 267, 367, 467, 567, 128, 138, 
      238, 148, 248, 348, 158, 258, 358, 458, 168, 268, 368, 468, 568, 178, 
      278, 378, 478, 578, 678, 129, 139, 239, 149, 249, 349, 159, 259, 359,
      459, 169, 269, 369, 469, 569, 179, 279, 379, 479, 579, 679, 189, 289, 
      389, 489, 589, 689, 789, 1234, 1235, 1245, 1345, 2345, 1236, 1246, 1346, 
      2346, 1256, 1356, 2356, 1456, 2456, 3456, 1237, 1247, 1347, 2347, 1257, 
      1357, 2357, 1457, 2457, 3457, 1267, 1367, 2367, 1467, 2467, 3467, 1567, 
      2567, 3567, 4567, 1238, 1248, 1348, 2348, 1258, 1358, 2358, 1458, 2458, 
      3458, 1268, 1368, 2368, 1468, 2468, 3468, 1568, 2568, 3568, 4568, 1278, 
      1378, 2378, 1478, 2478, 3478, 1578, 2578, 3578, 4578, 1678, 2678, 3678,
      4678, 5678, 1239, 1249, 1349, 2349, 1259, 1359, 2359, 1459, 2459, 3459, 
      1269, 1369, 2369, 1469, 2469, 3469, 1569, 2569, 3569, 4569, 1279, 1379,
      2379, 1479, 2479, 3479, 1579, 2579, 3579, 4579, 1679, 2679, 3679, 4679, 
      5679, 1289, 1389, 2389, 1489, 2489, 3489, 1589, 2589, 3589, 4589, 1689, 
      2689, 3689, 4689, 5689, 1789, 2789, 3789, 4789, 5789, 6789, 12345, 12346,
      12356, 12456, 13456, 23456, 12347, 12357, 12457, 13457, 23457, 12367, 
      12467, 13467, 23467, 12567, 13567, 23567, 14567, 24567, 34567, 12348, 
      12358, 12458, 13458, 23458, 12368, 12468, 13468, 23468, 12568, 13568,
      23568, 14568, 24568, 34568, 12378, 12478, 13478, 23478, 12578, 13578, 
      23578, 14578, 24578, 34578, 12678, 13678, 23678, 14678, 24678, 34678, 
      15678, 25678, 35678, 45678, 12349, 12359, 12459, 13459, 23459, 12369, 
      12469, 13469, 23469, 12569, 13569, 23569, 14569, 24569, 34569, 12379, 
      12479, 13479, 23479, 12579, 13579, 23579, 14579, 24579, 34579, 12679,
      13679, 23679, 14679, 24679, 34679, 15679, 25679, 35679, 45679, 12389,
      12489, 13489, 23489, 12589, 13589, 23589, 14589, 24589, 34589, 12689, 
      13689, 23689, 14689, 24689, 34689, 15689, 25689, 35689, 45689, 12789, 
      13789, 23789, 14789, 24789, 34789, 15789, 25789, 35789, 45789, 16789,
      26789, 36789, 46789, 56789, 123456, 123457, 123467, 123567, 124567, 
      134567, 234567, 123458, 123468, 123568, 124568, 134568, 234568, 123478, 
      123578, 124578, 134578, 234578, 123678, 124678, 134678, 234678, 125678, 
      135678, 235678, 145678, 245678, 345678, 123459, 123469, 123569, 124569, 
      134569, 234569, 123479, 123579, 124579, 134579, 234579, 123679, 124679, 
      134679, 234679, 125679, 135679, 235679, 145679, 245679, 345679, 123489, 
       123589, 124589, 134589, 234589, 123689, 124689, 134689, 234689, 125689,
      135689, 235689, 145689, 245689, 345689, 123789, 124789, 134789, 234789,
      125789, 135789, 235789, 145789, 245789, 345789, 126789, 136789, 236789,
      146789, 246789, 346789, 156789, 256789, 356789, 456789, 1234567, 1234568,
      1234578, 1234678, 1235678, 1245678, 1345678, 2345678, 1234569, 1234579, 
      1234679, 1235679, 1245679, 1345679, 2345679, 1234589, 1234689, 1235689,
      1245689, 1345689, 2345689, 1234789, 1235789, 1245789, 1345789, 2345789, 
      1236789, 1246789, 1346789, 2346789, 1256789, 1356789, 2356789, 1456789, 
      2456789, 3456789, 12345678, 12345679, 12345689, 12345789, 12346789, 
      12356789, 12456789, 13456789, 23456789, 123456789]

In the above method, you have to record the position of the each digits. Actually the count of result is 511 which equals the sum of combination of the following array: [1,2,3,4,5,6,7,8,9].

You just select an arbitrary number of numbers out of the array, because they are all different so there is only one ascending order. Thus the question has been transformed to calculate the the sum of combination of above array.

 result =     C9(1) + C9(2) + C9(3) + C9(4) + C9(5) + C9(6) + C9(7) + C9(8) + C9(9)

There are many ways to calculate this and also easily recursive without memorizing their last digits.

Answer 3

This is just a combination problem. Python has this written already in itertools.

from itertools import combinations 

numbers=[1,2,3,4,5,6,7,8,9] 
length=[2,3,4,5,6,7,8,9]
for L in length:
    comb=combinations(numbers,L)
    for i in list(comb):
        num=0
        for n in range(len(i)):
            num=i[n]*10**(len(i)-n-1)+num
        print(num)

I start by defining the numbers available to use numbers=[1,2,3,4,5,6,7,8,9] then define the lengths I'm interested in (everything but 1). combinations from itertools then returns all possible combinations for a given length.

The next section just takes the tuple of combinations eg (2,5,6,7), and changes them into the actual number 2567.

for i in list(comb):
    num=0
    for n in range(len(i)):
        num=i[n]*10**(len(i)-n-1)+num
    print(num)