2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ As far as I get it, the problem does not require you to solve it on numbers. Why don't you solve it on strings/arrays of characters then? The output is text anyway. \$\endgroup\$ – CiaPan Apr 2 at 10:31
  • \$\begingroup\$ @CiaPan Your comment implies that it would somehow be easier to solve it on strings. How and why would I do it with a string of characters? \$\endgroup\$ – Lucas Raphael Pianegonda Apr 2 at 10:40
  • \$\begingroup\$ @LucasRaphaelPianegonda Just compare the integer codes for each digit character in the string. It makes it much simpler. It likely isn't as performant, but that probably isn't a concern. If you can read lisps, here's a predicate that can simply be looped over: gist.github.com/carcigenicate/d490f8284427b3b5db9da76c71bece43 \$\endgroup\$ – Carcigenicate Apr 2 at 22:03
  • 1
    \$\begingroup\$ Please note there are only 9 single-digit numbers (zero skipped), all of which are 'increasing', but there are 90 two-digits numbers and just 40 of them are increasing, which is 2/5. And in three-digits numbers only about 1/10.7 are increasing (84 out of 900). In the worst case you have just one increasing number among almost a billion of all 9-digit numbers. That's why your code is inefficient for bigger N values, and explicit construction should be faster. \$\endgroup\$ – CiaPan Apr 3 at 8:27
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It doesn't yield all solutions: example: N=3; 123,124,... 129, 139, 149, 159... but 134 is also a solution that doesn't appear in this algorithm. You'd need to go from 129 to 134 then count up 135,136 ... 139, then increase to 145,146, until 149 then 156 ect. \$\endgroup\$ – Lucas Raphael Pianegonda Apr 2 at 10:35
  • \$\begingroup\$ @LucasRaphaelPianegonda Added an edit for further explanation. \$\endgroup\$ – QuantumChris Apr 2 at 11:09
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Welcome to codereview NAP_time. The question was about Visual Basic, an answer using python might not be helpful to the OP, depending on their skillset. \$\endgroup\$ – Harald Scheirich Apr 3 at 11:56
  • \$\begingroup\$ Fair enough. I guess I assumed that visual basic might have something similar. At the least, searching for combinations code will probably turn something up. \$\endgroup\$ – NAP_time Apr 3 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.