алгоритм для решения поставленной задачи

Question

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

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

Примером может быть:

, если х представляет собой набор чисел от 1 до 100, и у меня есть четыре подмножества:

• а = 0-49
• б = 50-100
• с = 50-75
• д = 76-100

то possib Комбинации ле будет:

• а + б
• а + с + д

Answer 1

Опишите, что вы назвали проблемой Exact cover. Общее решение - это Knuth's Algorithm X, при этом алгоритм Dancing Links является конкретной реализацией.

Answer 2

Способ (не может быть лучшим способом) является:

1. Создать набор все пары подмножеств, которые перекрываются.
2. Для каждой комбинации исходных подмножеств, скажем, «ложь», если комбинация содержит одну или несколько пар, перечисленных в шаге 1, иначе скажем «истина», если объединение подмножеств равно x (например, если общее число элементы в подмножествах x)

Answer 3

Фактический алгоритм в значительной степени зависит от выбора подмножеств, операции с продуктом и приравнивания операции. Для добавления (+) кажется, что вы можете найти summation в соответствии с вашими потребностями (сумма от 1 до 100 похожа на ваш пример a + b). Если вы можете это сделать, ваш алгоритм, очевидно, O (1).

Если у вас есть более жесткий продукт или приравнивающий оператор (допустим, взятие произведения двух терминов означает суммирование строк и поиск SHA-1-хэша), вы можете застревать вложенными петлями, что было бы O (n^x), где x - число членов/переменных.

Answer 4

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

Если вы говорите случайные подмножества, не обязательно диапазон, то предложение Ник Джонсон, вероятно, будет лучшим выбором.

Answer 5

Учитывая хорошо порядок на элементах х (сделать один, если это необходимо, это всегда возможно для конечных или счетных множеств):

Пусть «устанавливает выбранные до сих пор» быть пустым. Рассмотрим наименьший элемент x. Найти все наборы, которые содержат х и которые не пересекаются ни с одним из выбранных до сих пор множеств. Для каждого такого набора, в свою очередь, recurse, добавляя выбранный набор к «наборам, выбранным до сих пор», и глядя на наименьший элемент x не в любом выбранном наборе.Если вы достигнете точки, в которой нет элемента x слева, вы нашли решение. Если вы достигнете точки, в которой нет неубранного набора, содержащего искомый элемент и который не пересекается с любым из уже выбранных вами наборов, то вам не удалось найти решение, поэтому откат.

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

Answer 6

здесь плохой способ (рекурсивный, делает много избыточной работы). Но, по крайней мере, его фактический код и, вероятно, на полпути к «эффективному» решению.

def unique_sets(sets, target): 
    if not sets and not target: 
     yield [] 
    for i, s in enumerate(sets): 
     intersect = s.intersection(target) and not s.difference(target) 
     sets_without_s = sets[:i] + sets[i+1:] 
     if intersect: 
      for us in unique_sets(sets_without_s, target.difference(s)): 
       yield us + [s] 
     else: 
      for us in unique_sets(sets_without_s, target): 
       yield us 

class named_set(set): 
    def __init__(self, items, name): 
     set.__init__(self, items) 
     self.name = name 

    def __repr__(self): 
     return self.name 

a = named_set(range(0, 50), name='a') 
b = named_set(range(50, 100), name='b') 
c = named_set(range(50, 75), name='c') 
d = named_set(range(75, 100), name='d') 

for s in unique_sets([a,b,c,d], set(range(0, 100))): 
    print s