Оптимизация генератора перестановок, где сумма каждой перестановки равна одному и тому же значению

Вот один из способов разбить это на две подзадачи:

1. Найдите все ограниченные целочисленные разбиения target_sum на sample_size слагаемых s.t. все слагаемые происходят от set_of_number.
2. Вычислить перестановки мультимножества для каждого раздела (занимает большую часть времени).

Проблема 1 может быть решена с помощью динамического программирования. Я использовал multiset_permutations из sympy для части 2, хотя вы могли бы улучшить производительность, написав свой собственный код numba.

Вот код:

from functools import lru_cache
from sympy.utilities.iterables import multiset_permutations

@lru_cache(None)
def restricted_partitions(n, k, *xs):
  'partitions of n into k summands using only elements in xs (assumed positive integers)'
  if n == k == 0:
    # case of unique empty partition
    return [[]]
  elif n <= 0 or k <= 0 or not xs:
    # case where no partition is possible
    return []
  # general case
  result = list()
  x = xs[0] # element x we consider including in a partition
  i = 0     # number of times x should be included
  while True:
    i += 1
    if i > k or x * i > n:
      break
    for rest in restricted_partitions(n - x * i, k - i, *xs[1:]):
      result.append([x] * i + rest)
  result.extend(restricted_partitions(n, k, *xs[1:]))

  return result
    
def buildPerms2(sample_size, desired_sum, set_of_number):
  for part in restricted_partitions(desired_sum, sample_size, *set_of_number):
    yield from multiset_permutations(part)


# %timeit sum(1 for _ in buildPerms2(8, 16, [1, 2, 3, 4])) # 16 ms
# %timeit sum(1 for _ in buildPerms (8, 16, [1, 2, 3, 4])) # 604 ms

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

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

# present in the builtin math library for Python 3.8+
@lru_cache(None)
def binomial(n, k):
  if k == 0:
    return 1
  if n == 0:
    return 0
  return binomial(n - 1, k) + binomial(n - 1, k - 1)


@lru_cache(None)
def perm_counts(n, k, *xs):
  if n == k == 0:
    # case of unique empty partition
    return 1
  elif n <= 0 or k <= 0 or not xs:
    # case where no partition is possible
    return 0
  # general case
  result = 0
  x = xs[0] # element x we consider including in a partition
  i = 0     # number of times x should be included
  while True:
    i += 1
    if i > k or x * i > n:
      break
    result += binomial(k, i) * perm_counts(n - x * i, k - i, *xs[1:])

  result += perm_counts(n, k, *xs[1:])

  return result

# assert perm_counts(15, 6, *[1,2,3,4]) == sum(1 for _ in buildPerms2(6, 15, [1,2,3,4])) == 580
# perm_counts(1000, 100, *[1,2,4,8,16,32,64])
# 902366143258890463230784240045750280765827746908124462169947051257879292738672

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

result += binomial(k, i) * perm_counts(n - x * i, k - i, *xs[1:])

Есть i копий x для включения и k возможных позиций, где могут оказаться x. Чтобы учесть эту множественность, количество способов решения рекурсивной подзадачи умножается на k выберите i.