Как подсчитать целые числа между большими A и B с определенным свойством?

Ответ 1

Действительно, есть подход к этой схеме, которая, как оказалось, работает довольно часто. Он также может использоваться для перечисления всех X с данным свойством при условии, что их число достаточно мало. Вы можете даже использовать его для агрегирования некоторого ассоциативного оператора по всему X с заданным свойством, например, чтобы найти их сумму.

Чтобы понять общую идею, постараемся сформулировать условие X ≤ Y в терминах десятичных представлений X и Y.

Скажем, мы имеем X = x ₁ x ₂... x _{n - 1} x _n и Y = y ₁ y ₂... y _{n - 1} y _n, где x _i и y _i - это десятичные цифры X и Y. Если числа имеют разную длину, мы всегда можем добавить нулевые цифры в начало более короткого.

Определим leftmost_lo как наименьший я с x _i < у <суб > явспом > . Определим leftmost_lo как n + 1, если такого я не существует. Аналогично, мы определяем leftmost_hi как наименьший я с x _i > y _i, или n + 1 в противном случае.

Теперь X ≤ Y истинно, если и точно, если leftmost_lo <= leftmost_hi. С этим наблюдением становится возможным применить подход динамического программирования к проблеме, который "устанавливает" цифры X один за другим. Я продемонстрирую это с вашими примерами проблем:

Вычислить число f (Y) целых чисел X со свойством X ≤ Y и X имеет цифру sum 60

Пусть n - число Y-цифр, а y[i] - i-я десятичная цифра Y в соответствии с вышеприведенным определением. Следующий рекурсивный алгоритм решает проблему:

count(i, sum_so_far, leftmost_lo, leftmost_hi):
    if i == n + 1:
        # base case of the recursion, we have recursed beyond the last digit
        # now we check whether the number X we built is a valid solution
        if sum_so_far == 60 and leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    # we need to decide which digit to use for x[i]
    for d := 0 to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        if d < y[i] and i < leftmost_lo': leftmost_lo' = i
        if d > y[i] and i < leftmost_hi': leftmost_hi' = i
        result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi')
    return result

Теперь мы имеем f(Y) = count(1, 0, n + 1, n + 1), и мы решили проблему. Мы можем добавить memoization функцию, чтобы сделать ее быстрой. Время выполнения - O (n ⁴) для этой конкретной реализации. На самом деле мы можем искусно оптимизировать идею, чтобы сделать ее O (n). Это остается как упражнение для читателя (Подсказка: вы можете сжать информацию, хранящуюся в leftmost_lo и leftmost_hi, в один бит, и вы можете обрезать, если sum_so_far > 60). Решение можно найти в конце этого сообщения.

Если вы внимательно смотрите, sum_so_far здесь просто пример произвольной функции, вычисляющей значение из цифровой последовательности X. Это может быть любая функция, которая может быть вычислена цифрой по цифре и выводит достаточно небольшой результат. Это может быть произведение цифр, битовая маска набора цифр, которые выполняют определенное свойство или многое другое.

Он также может быть просто функцией, которая возвращает 1 или 0, в зависимости от того, содержит ли число только цифры 4 и 7, что разрешает второй пример тривиально. Мы должны быть немного осторожны, потому что нам разрешено иметь начальные нули в начале, поэтому нам нужно нести дополнительный бит через рекурсивные вызовы функций, говорящие нам, разрешено ли нам использовать нуль в качестве цифры.

Вычислить число f (Y) целых чисел X со свойством X ≤ Y и X является палиндромным

Это немного жестче. Нам нужно быть осторожным с ведущими нулями: зеркальная точка палиндромного числа зависит от того, сколько у нас ведущих нулей, поэтому нам нужно будет отслеживать количество ведущих нулей.

Существует несколько способов упростить это: если мы можем подсчитать f (Y) с дополнительным ограничением, чтобы все числа X должны иметь одинаковые цифры, такие как Y, тогда мы также можем решить исходную проблему, путем повторения всех возможных цифр и добавления результатов.

Итак, мы можем просто предположить, что у нас нет ведущих нулей:

count(i, leftmost_lo, leftmost_hi):
    if i == ceil(n/2) + 1: # we stop after we have placed one half of the number
        if leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    start = (i == 1) ? 1 : 0    # no leading zero, remember?
    for d := start to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        # digit n - i + 1 is the mirrored place of index i, so we place both at 
        # the same time here
        if d < y[i]     and i     < leftmost_lo': leftmost_lo' = i
        if d < y[n-i+1] and n-i+1 < leftmost_lo': leftmost_lo' = n-i+1
        if d > y[i]     and i     < leftmost_hi': leftmost_hi' = i
        if d > y[n-i+1] and n-i+1 < leftmost_hi': leftmost_hi' = n-i+1
        result += count(i + 1, leftmost_lo', leftmost_hi')
    return result

Результат снова будет f(Y) = count(1, n + 1, n + 1).

ОБНОВЛЕНИЕ:. Если мы хотим не только подсчитать числа, но и, возможно, перечислим их или вычислим из них какую-то совокупную функцию, которая не раскрывает структуру группы, нам необходимо обеспечить соблюдение нижней границы X также во время рекурсии. Это добавляет еще несколько параметров.

ОБНОВЛЕНИЕ 2: O (n) Решение для примера "цифра суммы 60":

В этом приложении мы поместим цифры слева направо. Поскольку нас интересует только то, имеет ли значение leftmost_lo < leftmost_hi, добавим новый параметр lo. lo истинно iif leftmost_lo < i и false в противном случае. Если lo истинно, мы можем использовать любую цифру для позиции i. Если это ложь, мы можем использовать цифры 0 только для Y [i], так как любая более крупная цифра вызывает leftmost_hi = i < leftmost_lo и поэтому не может привести к решению. Код:

def f(i, sum_so_far, lo):
    if i == n + 1: return sum_so_far == 60
    if sum_so_far > 60: return 0
    res = 0
    for d := 0 to (lo ? 9 : y[i]):
         res += f(i + 1, sum + d, lo || d < y[i])
    return res

Возможно, этот способ взгляда на это несколько проще, но также немного менее явный, чем подход leftmost_lo/leftmost_hi. Он также не работает сразу для нескольких более сложных сценариев, таких как проблема палиндрома (хотя его также можно использовать там).