Ведущее число групп между двумя числами

Question

(Python) Даны два числа А и В. Мне нужно найти все вложенные «группы» чисел:

range(2169800, 2171194) 

leading numbers: 21698XX, 21699XX, 2170XX, 21710XX, 217110X, 217111X, 
217112X, 217113X, 217114X, 217115X, 217116X, 217117X, 217118X, 2171190X, 
2171191X, 2171192X, 2171193X, 2171194X 

или как это:

range(1000, 1452) 

leading numbers: 10XX, 11XX, 12XX, 13XX, 140X, 141X, 142X, 143X, 
144X, 1450, 1451, 1452 

Answer 1

Сложнее, чем это было в первый раз - довольно уверен, что это сплошное и будет обрабатывать большинство граничных условий. :) (There are few !!)

def leading(a, b): 
    # generate digit pairs a=123, b=456 -> [(1, 4), (2, 5), (3, 6)] 
    zip_digits = zip(str(a), str(b)) 
    zip_digits = map(lambda (x,y):(int(x), int(y)), zip_digits) 

    # this ignores problems where the last matching digits are 0 and 9 
    # leading (12000, 12999) is same as leading(12, 12) 
    while(zip_digits[-1] == (0,9)):   
     zip_digits.pop()    

    # start recursion 
    return compute_leading(zip_digits) 

def compute_leading(zip_digits): 
    if(len(zip_digits) == 1): # 1 digit case is simple!! :) 
     (a,b) = zip_digits.pop() 
     return range(a, b+1) 

    #now we partition the problem 
    # given leading(123,456) we decompose this into 3 problems 
    # lows -> leading(123,129) 
    # middle -> leading(130,449) which we can recurse to leading(13,44) 
    # highs -> leading(450,456) 

    last_digits = zip_digits.pop() 
    low_prefix = reduce(lambda x, y : 10 * x + y, [tup[0] for tup in zip_digits]) * 10  # base for lows e.g. 120 
    high_prefix = reduce(lambda x, y : 10 * x + y, [tup[1] for tup in zip_digits]) * 10  # base for highs e.g. 450 
    lows = range(low_prefix + last_digits[0], low_prefix + 10) 
    highs = range(high_prefix + 0, high_prefix + last_digits[1] + 1) 

    #check for boundary cases where lows or highs have all ten digits 
    (a,b) = zip_digits.pop() # pop last digits of middle so they can be adjusted 
    if len(lows) == 10: 
     lows = [] 
    else: 
     a = a + 1 

    if len(highs) == 10: 
     highs = [] 
    else: 
     b = b - 1 

    zip_digits.append((a,b)) # push back last digits of middle after adjustments 

    return lows + compute_leading(zip_digits) + highs  # and recurse - woohoo!! 



print leading(199,411) 

print leading(2169800, 2171194) 

print leading(1000, 1452) 

Answer 2

Это должен дать вам хорошую отправную точку:

def leading(start, end): 

    leading = [] 
    hundreds = start // 100 

    while (end - hundreds * 100) > 100: 
     i = hundreds * 100 
     leading.append(range(i,i+100)) 
     hundreds += 1 

    c = hundreds * 100 
    tens = 1 

    while (end - c - tens * 10) > 10: 
     i = c + tens * 10 
     leading.append(range(i, i + 10)) 
     tens += 1 

    c += tens * 10 
    ones = 1 

    while (end - c - ones) > 0: 
     i = c + ones 
     leading.append(i) 
     ones += 1 

    leading.append(end) 

    return leading 

Хорошо, все может быть на одном уровне уровня петли. Но я подумал, что это может быть яснее. Надеюсь, это поможет вам ...

Обновление: Теперь я вижу, что вы хотите. Кроме того, код Марии, похоже, не работает для меня. (К сожалению ...) Поэтому, пожалуйста, рассмотрим следующий код:

def leading(start, end): 

    depth = 2 
    while 10 ** depth > end : depth -=1 
    leading = [] 
    const = 0 
    coeff = start // 10 ** depth 

    while depth >= 0: 
     while (end - const - coeff * 10 ** depth) >= 10 ** depth: 
      leading.append(str(const/10 ** depth + coeff) + "X" * depth) 
      coeff += 1 

     const += coeff * 10 ** depth 
     coeff = 0 
     depth -= 1 

    leading.append(end) 

    return leading 

print leading(199,411) 

print leading(2169800, 2171194) 

print leading(1000, 1453) 

print leading(1,12) 

Теперь, позвольте мне попытаться объяснить подход здесь. Алгоритм попытается найти «конец», начиная со значения «start» и проверить, находится ли «конец» в следующих 10^2 (что в данном случае равно 100). Если он терпит неудачу, он совершит скачок 10^2 до тех пор, пока он не удастся. Когда это удастся, он пойдет на один уровень глубины ниже. То есть, он сделает скачки на порядок меньше. И петля таким образом, пока глубина не будет равна нулю (= прыжки 10^0 = 1). Алгоритм останавливается, когда он достигает значения «end».

Вы также можете заметить, что у меня реализован цикл обертывания, о котором я упомянул, поэтому теперь можно определить начальную глубину (или размер прыжка) в переменной.

Первый цикл while гарантирует, что первый прыжок не превысит значение «end».

Если у вас есть какие-либо вопросы, просто не стесняйтесь спрашивать.

Answer 3

def foo(start, end): 
    index = 0 
    is_lower = False 
    while index < len(start): 
     if is_lower and start[index] == '0': 
      break 
     if not is_lower and start[index] < end[index]: 
      first_lower = index 
      is_lower = True 
     index += 1 
    return index-1, first_lower 


start = '2169800' 
end = '2171194' 
result = [] 
while int(start) < int(end): 
    index, first_lower = foo(start, end) 
    range_end = index > first_lower and 10 or int(end[first_lower]) 
    for x in range(int(start[index]), range_end): 
     result.append(start[:index] + str(x) + 'X'*(len(start)-index-1)) 
    if range_end == 10: 
     start = str(int(start[:index])+1)+'0'+start[index+1:] 
    else: 
     start = start[:index] + str(range_end) + start[index+1:] 

result.append(end) 
print "Leading numbers:" 
print result 

Я тестирую примеры, которые вы указали, это правильно. Надеюсь, это вам поможет