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

Я хочу создать список перестановок или декартовых произведений (не уверен, какой из них применим здесь), где сумма значений в каждой перестановке составляет указанное значение.

Для функции должно быть три параметра.

  1. Размер образца: Количество элементов в каждой перестановке
  2. Желаемая сумма: Общее количество, которое должна составлять каждая перестановка
  3. Набор чисел: Набор чисел, которые могут быть включены с повторением в перестановки

У меня есть реализация, работающая ниже, но она кажется довольно медленной. Я бы предпочел использовать итератор для потоковой передачи результатов, но мне также понадобится функция, которая сможет вычислить общее количество элементов, которые будет производить итератор.

def buildPerms(sample_size, desired_sum, set_of_number):
    blank = [0] * sample_size
    return recurseBuildPerms([], blank, set_of_number, desired_sum)

def recurseBuildPerms(perms, blank, values, desired_size, search_index = 0):
    for i in range(0, len(values)):
        for j in range(search_index, len(blank)):
            if(blank[j] == 0):
                new_blank = blank.copy()
                new_blank[j] = values[i]
                remainder = desired_size - sum(new_blank)
                new_values = list(filter(lambda x: x <=  remainder, values))
                if(len(new_values) > 0):
                    recurseBuildPerms(perms, new_blank, new_values, desired_size, j)
                elif(sum(new_blank) <= desired_size):
                    perms.append( new_blank)
    return perms

perms = buildPerms(4, 10, [1,2,3])
print(perms)
## Output
[[1, 3, 3, 3], [2, 2, 3, 3], [2, 3, 2, 3], 
 [2, 3, 3, 2], [3, 1, 3, 3], [3, 2, 2, 3], 
 [3, 2, 3, 2], [3, 3, 1, 3], [3, 3, 2, 2], 
 [3, 3, 3, 1]]


https://www.online-python.com/9cmOev3zlg

Вопросы:

  1. Может ли кто-нибудь помочь мне преобразовать мое решение в итератор?
  2. Можно ли вычислить общее количество элементов, не видя полного списка?

Для подсчета: здесь - это связанный вопрос, который решает упрощенную версию суммы подмножества (я не уверен, что ваша проблема проще, и поэтому ее можно решить намного эффективнее).

Jérôme Richard 09.04.2022 18:20

Спасибо, сейчас я посмотрю на библиотеку numba и посмотрю, насколько это улучшит время выполнения.

mullin 10.04.2022 01:40
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
2
2
40
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

  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.

Спасибо за эти ответы, я собираюсь провести несколько тестов на них. Причина, по которой в моем решении нет нулей, заключается в том, что я использую нули в качестве базовой или пустой ячейки, что приведет к тому, что все нулевые перестановки будут рассчитаны по своей сути. Для первого шага это все комбинации, которые в сумме составляют «target_sum»?

mullin 10.04.2022 08:27

Имеет смысл. Шаг 1 (restricted_partitions(k, n, xs)) должен предоставить все способы выбора k элементов из xs с повторением этой суммы до n, игнорируя порядок.

hilberts_drinking_problem 10.04.2022 08:33

И последнее, что я только что запустил np.unique(output, axis=0) на обоих наших выходах, и похоже, что выходы уменьшаются. Возможно, я не понимаю, что делает np.unique, но если он просто сокращается до уникальных строк, размер вывода должен оставаться прежним. Что вы думаете по этому поводу?

mullin 10.04.2022 09:54
np.unique не обрабатывает векторные входные данные. Вы можете использовать .drop_duplicates на pandas.DataFrame(output) или set(tuple(x) for x in output), чтобы сравнить результаты. Повторных перестановок быть не должно.
hilberts_drinking_problem 10.04.2022 10:06

Другие вопросы по теме