Какой замечательный вопрос!Чтобы соответствовать терминологии, я буду ссылаться на строки в вашей матрице как «входные данные сумки », а элементы во входных пакетах - как «объекты».Сумка (или мультимножество) - это контейнер, который позволяет членам появляться более одного раза, но у которых нет внутреннего порядка (в отличие от списков).
Мы ищем функцию со следующей подписью:
set of valid combinations =
generate_combinations(list of input bags, number of objects in valid combination)
Поскольку возможно, что набор допустимых комбинаций превышает объем памяти, доступной для Python, generate_combinations должен возвращать генератор, а не явный список.
Действительный результат должен удовлетворять следующемутребования:
- Минимум 1 объект из каждой входной сумки
- Всего будет n объектов
Я предполагаю следующее:
- Порядок объектов в результате не имеет значения
- Входная сумка может содержать дубликаты объектов
- Две входные сумки могут содержать дубликаты объектов (в вырожденном случае два входных пакетаможет быть идентичным)
- Действительный результат извлекает объекты без замены
Требование № 1 и Предположение № 4 подразумевают number of input bags <= n <= total number of objects in all bags
Data Structures
- Поскольку входные пакеты могут содержать повторяющиеся значения (согласно предположению № 2), мы не можем использовать set / frozenset для их хранения.Списки Python подходят для этой задачи.Альтернативным контейнером может быть collection.Counter , который имеет тест членства в постоянном времени и лучшую пространственную эффективность для списков с множеством дубликатов.
- Каждая допустимая комбинация также является сумкой
- Заказ не имеет значения для списка входных пакетов, поэтому его можно обобщить как пакет входных пакетов.Для здравого смысла я оставлю все как есть.
Я буду использовать встроенный в Python модуль itertools для генерации комбинаций, который был представлен в v2.6.Если вы используете старую версию Python, используйте рецепт.Для этих примеров кода я неявно преобразовал генераторы в списки для ясности.
>>> import itertools, collections
>>> input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
>>> output_bag_size = 5
>>> combos = generate_combinations(input_bags, output_bag_size)
>>> combos.next() #an arbitrary example
Bag([1,1,2,4,12])
Поймите, что проблема, как указано выше, может быть уменьшена до проблемы, которая немедленно решается встроенным в Python модулем itertools, которыйгенерирует комбинации последовательностей.Единственная модификация, которую нам нужно сделать, это исключить Требование № 1.Чтобы решить уменьшенные проблемы, объедините элементы сумок в одну сумку.
>>> all_objects = itertools.chain.from_iterable(input_bags)
>>> all_objects
generator that returns [1, 2, 2, 3, 5, 1, 4, 5, 9, 12]
>>> combos = itertools.combinations(all_objects, output_bag_size)
>>> combos
generator that returns [(1,2,2,3,5), (1,2,2,3,1), (1,2,2,3,4), ...]
Чтобы восстановить требование № 1, каждая действительная комбинация (выходная сумка) должна содержать 1 элемент из каждой входной сумки плюс дополнительныеэлементы из любого из пакетов, пока размер выходного пакета не достигнет указанного пользователем значения.Если перекрытие между [1 элементом из каждого входного пакета] и [дополнительными элементами из любого из пакетов] игнорируется, решение представляет собой просто декартово произведение возможных комбинаций первой и возможных комбинаций второй.
Чтобы справиться с перекрытием, удалите элементы из [1 элемента из каждого входного пакета] из [дополнительных элементов из любого из пакетов] и удалите петлю.
>>> combos_with_one_element_from_each_bag = itertools.product(*input_bags)
>>> for base_combo in combos_with_one_element_from_each_bag:
>>> all_objects = list(itertools.chain.from_iterable(input_bags))
>>> for seen in base_combo:
>>> all_objects.remove(seen)
>>> all_objects_minus_base_combo = all_objects
>>> for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
>>> yield itertools.chain(base_combo, remaining_combo)
Операция удаленияподдерживается в списках, но не поддерживается в генераторах.Чтобы избежать сохранения всех объектов в памяти в виде списка, создайте функцию, которая пропускает элементы в base_combo.
>>> def remove_elements(iterable, elements_to_remove):
>>> elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
>>> for item in iterable:
>>> if item not in elements_to_remove_copy:
>>> yield item
>>> else:
>>> elements_to_remove_copy.remove(item)
Реализация класса Bag может выглядеть следующим образом:
>>> class Bag(collections.Counter):
>>> def __iter__(self):
>>> return self.elements()
>>> def remove(self, item):
>>> self[item] -= 1
>>> if self[item] <= 0:
>>> del self[item]
Полный код
import itertools, collections
class Bag(collections.Counter):
def __iter__(self):
return self.elements()
def remove(self, item):
self[item] -= 1
if self[item] <= 0:
del self[item]
def __repr__(self):
return 'Bag(%s)' % sorted(self.elements())
def remove_elements(iterable, elements_to_remove):
elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
for item in iterable:
if item not in elements_to_remove_copy:
yield item
else:
elements_to_remove_copy.remove(item)
def generate_combinations(input_bags, output_bag_size):
combos_with_one_element_from_each_bag = itertools.product(*input_bags)
for base_combo in combos_with_one_element_from_each_bag:
all_objects_minus_base_combo = remove_elements(itertools.chain.from_iterable(input_bags), base_combo)
for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
yield Bag(itertools.chain(base_combo, remaining_combo))
input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
output_bag_size = 5
combos = generate_combinations(input_bags, output_bag_size)
list(combos)
Завершите это, добавив код проверки ошибок (такой как output_bag_size> = len (input_bags).
Преимущества этого подхода: 1. Меньше кода для поддержки (а именно itertools) 2. Нет рекурсии. Производительность Python снижается с высотой стека вызовов, поэтому минимизация рекурсии выгодна 3. Минимальное потребление памяти. Этот алгоритм требует постоянной памяти, превышающей то, что используется спискомвходные пакеты.