Предположим, у вас есть код для создания всех решений.
(Для параметра г здесь, проходят 9. Это число на правой части неравенств. Обратите внимание, что этот код работает только тогда, когда г положительна.)
from math import floor, ceil
def iter_solutions(r, n, z):
c = [None] * n
def iter_solutions_bounded(k, pick):
# pick is the last pick, if any, and 0 otherwise
assert (1 <= k < n and pick == c[k]) or (k == n and pick == 0)
min_ck = int(ceil(-pick/r))
max_ck = int(floor((z - pick)/r))
if k == 1:
for ck in range(max(min_ck, 0), min(max_ck, z) + 1):
c[0] = ck
yield c
else:
for ck in range(min_ck, max_ck + 1):
c[k - 1] = ck
for soln in iter_solutions_bounded(k - 1, ck):
yield soln
return iter_solutions_bounded(n, 0)
Вы можете преобразовать это в код, который просто считает решениями, просто удалив весь код, относящийся к c, и добавит количество решений, которые были бы получены. Наконец, вы можете улучшить производительность с помощью memoization.
from math import floor, ceil
def memoize(f):
cache = {}
def g(*args):
if args in cache:
return cache[args]
tmp = cache[args] = f(*args)
return tmp
return g
def len_range(a, b):
if a <= b:
return b - a
return 0
def count_solutions(r, n, z):
@memoize
def count_solutions_bounded(k, pick):
min_ck = int(ceil(-pick/r))
max_ck = int(floor((z - pick)/r))
if k == 1:
return len_range(max(min_ck, 0), min(max_ck, z) + 1)
else:
return sum(count_solutions_bounded(k - 1, ck) for ck in range(min_ck, max_ck + 1))
return count_solutions_bounded(n, 0)
Некоторые возможные улучшения:
Если это правда, что с ... с п всегда ≤ г, а затем обнаружения, что и сразу же возвращаются 0 поможет много для больших n. Фактически это сократило бы время работы до молниеносного O (nz).
Если предполагается, что с ... с п все неотрицательными, что даже лучше. Внесение соответствующих изменений в min_ck и max_ck сделает этот O (nz) с меньшей константой, а кеш может быть плоской 2D-матрицей вместо более медленной хеш-таблицы, которую я получил.
Возможно, вам удастся добиться большего, создав кэш систематически, вместо того, чтобы заполнять его «по требованию», как это делает код memoization. Сначала постройте весь кеш для n = 1, затем для n = 2 и т. Д. Таким образом, вы можете избежать рекурсии, и на каждом шаге вы можете выбросить кэшированные данные, которые вам больше не нужны (после вычисления результатов для n = 2 вам больше не нужны записи для n = 1).
Вы показываете матрицу 4x3, умноженную на матрицу 3x1. Поэтому результатом является матрица 4x1. Что значит сказать, что матрица 4x1 имеет хотя бы ноль и не более девяти? – jason
Пожалуйста, исправьте Q ... это напоминает мне смешанное целочисленное программирование, за исключением ... | Теперь, как насчет этого: лечить неравенства как полуплоскости, вычислить пересечение всех регионов - должен дать вам многоугольник. Если некоторые из его координат +/- бесконечность, то у вас либо есть бесконечное число, либо нулевые решения (я думаю). В противном случае найдите ограничительный прямоугольник. для многоугольника, сделайте два вложенных для него петель и проверьте, находится ли каждая точка внутри многоугольника (вам нужно будет триангулировать ее). Наихудший случай - ограничивающий прямоугольник O (n^2), но вы получаете O (n) решения. Вычислительная геометрия - ваш друг. –
Hm ... в этом конкретном примере вам нужно только перечислить (0,0,0) ... (9,9,9) (если матрица имеет неотрицательные целые числа) –