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

Question

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

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

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

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

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

тогда возможные комбинации будут:

• a + b
• a + c + d

Answer 1

То, что вы описываете, называется проблемой Точное покрытие . Общее решение - алгоритм Кнута X , а конкретная реализация - алгоритм Dancing Links .

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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