Блог

Главная - Вопросы по программированию - Получение перестановок взвешенных элементов, которые в сумме составляют определенную сумму

Получение перестановок взвешенных элементов, которые в сумме составляют определенную сумму

#python #permutation

Вопрос:

У меня есть элемент А весом 1, а элемент В весом 2. Мне нужно найти возможные перестановки A и B, которые в сумме составляют определенную сумму.

Например, когда желаемая сумма равна 4, я хотел бы получить следующее:

 [A, A, A, A] 
[B, B]  
[B, A, A]  
[A, B, A]  
[A, A, B]

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

Комментарии:

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

2. Спасибо! Похоже, это то, что я ищу. Я полагал, что решение уже существует, но я не мог подобрать правильные слова, чтобы найти его.

Ответ №1:

Это не перестановка, которую вы ищете, а комбинация. Перестановка — это перетасовка конечного набора элементов без повторений, в то время как комбинация-это каждое из n полей, предполагающее один из m элементов, который в python обозначается itertools.computations_with_replacement как . В терминах кодекса:

 import itertools
from functools import reduce

elements = {"A": 1, "B": 2, "C": 1}
sum_restriction = lambda x: sum(elements[i] for i in x)==4
max_els = 4 // min(elements.values())   1

res = reduce(lambda x,y:x y,[list(filter(sum_restriction, itertools.combinations_with_replacement(elements.keys(), i))) for i in range(max_els 1)])

Для моего примера возвращаются:

 >>> res
[('B', 'B'), ('A', 'A', 'B'), ('A', 'B', 'C'), ('B', 'C', 'C'), ('A', 'A', 'A', 'A'), ('A', 'A', 'A', 'C'), ('A', 'A', 'C', 'C'), ('A', 'C', 'C', 'C'), ('C', 'C', 'C', 'C')]

Ответ №2:

 from itertools import permutations, chain


def get_permutations_count_to_n(item_dict, n, max_items=4):
    """ For a given dict with items as keys and weights as values, return a set of permutations that have a combined weight of N
    :param item_dict: dictionary with items as keys and their weight as value 
    :param n: integer that should be the combined weight of permutated items
    :param max_items: the maximum number of items that may occur in a permutation """
    item_list = list(items.keys()) * max_items
    combs = [list(permutations(item_list, i)) for i in range(1, max_items 1)]
    filtered_combs = [comb for comb in chain.from_iterable(combs) if sum(item_dict[x] for x in comb) == n]
    return set(filtered_combs)

items = {'A': 1, 'B': 2}
get_permutations_count_to_n(items, n=4)
 
 >>> {('B', 'A', 'A'), ('B', 'B'), ('A', 'A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'B', 'A')}
Метки: ,