algorithm - 显示所有可能的数字，其数字按升序排列

Question

编写一个程序，可以显示给定两个数字之间所有可能的数字，其数字按升序排列。

例如:-

1. 输入:5000 到 6000

   Output: 5678 5679 5689 5789
   

2. 输入:90 到 124

   Output: 123 124
   

蛮力方法可以计算所有数字并检查每个数字的数字。但我想要的方法可以跳过一些数字并且可以带来低于 O(n) 的复杂性。是否存在可以为该问题提供更好方法的任何此类解决方案？

Answer 1

我提供了一个 Python 解决方案。它是有效的，因为它只考虑相关的数字。基本思想是向上计数，但处理溢出的方式有所不同。虽然我们通常将溢出的数字设置为 0，但这里我们将它们设置为前一个数字 +1。请查看内联评论以获取更多详细信息。你可以在这里玩:http://ideone.com/ePvVsQ

def ascending( na, nb ):
    assert nb>=na
    # split each number into a list of digits
    a = list( int(x) for x in str(na))
    b = list( int(x) for x in str(nb))

    d = len(b) - len(a)

    # if both numbers have different length add leading zeros 
    if d>0:
        a = [0]*d + a  # add leading zeros
    assert len(a) == len(b)
    n = len(a)


    # check if the initial value has increasing digits as required,
    # and fix if necessary
    for x in range(d+1, n):
        if a[x] <= a[x-1]:
            for y in range(x, n):
                a[y] = a[y-1] + 1
            break

    res = [] # result set

    while a<=b:
        # if we found a value and add it to the result list
        # turn the list of digits back into an integer
        if max(a) < 10:
            res.append( int( ''.join( str(k) for k in a ) ) )

        # in order to increase the number we look for the
        # least significant digit that can be increased
        for x in range( n-1, -1, -1): # count down from n-1 to 0
            if a[x] < 10+x-n:
                break
        # digit x is to be increased
        a[x] += 1
        # all subsequent digits must be increased accordingly
        for y in range( x+1, n ):
            a[y] = a[y-1] + 1

    return res

print( ascending( 5000, 9000 ) )