Минимальное подмножество, чтобы покрыть все наборы

Question

Нам предоставляется 5 различных наборов:

s1 = {a,b,c}
s2 = {c,d}
s3 = {a,g,h}
s4 = {d,e,f}
s5 = {g,k,l}

Цель состоит в том, чтобы найти минимальное количество предметов, чтобы каждый набор был представлен хотя бы один раз.В этом случае мы можем легко увидеть, что идеальное решение - {a,d,g}.Есть ли способ сделать это программно?

Редактировать: это то, что у меня есть (r - список наборов)

for i in r:
    i.sort()

r.sort(reverse=True)

arr = []

arr.append(r[0][0])

def isInArr(k):
    for j in k:
        if j in arr:
            return False
    return True

for i in r[1:]:
    if isInArr(i):
        arr.append(i[0])

Редактировать 2:

Этот код объединяет ответ Коннора и подкрепляет (насколько мне известно) оптимальное решение.

def isnotarr(k,rs):
    for j in k:
        if j in rs:
            return True
    return False

def most_frequent(List):
   return max(set(List), key = List.count)

##s1 = set(["a", "b", "c"])
##s2 = set(["c", "d"])
##s3 = set(["a", "g", "h"])
##s4 = set(["d", "e", "f"])
##s5 = set(["g", "k", "l"])
set_list = [set(i) for i in r]

return_set = []
while len(set_list) > 0:
   elements = []
   for s in set_list:
       for el in s:
           elements.append(el)
   element = most_frequent(elements)
   return_set.append(element)
   new_set_list = []
   for s in set_list:
       if element not in s:
           new_set_list.append(s)
   set_list = new_set_list

print "================initial set found============\n"
print(return_set)
print "================initial set found============\n"



def isvalidcomb(cm):
    for el in r:
        if isnotarr(el,cm):
            pass
        else:
            return False
    return True

def bfopt(n):
    combs = itertools.combinations(return_set,n)
    for i in combs:
        if isvalidcomb(i):
            return i
    return None

for i in range(len(return_set),0,-1):
    print "===========computing sets for maxlen %d============\n"%(i)
    tmp = bfopt(i)
    if tmp is not None:
        print tmp

Answer 1

Первый: каждый набор может быть представлен степенью 2: si = 2^(i-1).

Каждую букву можно считать элементом с весом 1, имеющим определенное значение.

Значениебуквы можно оценить как сумму наборов, которые она представляет.

например: a представляет s1 и s3 , поэтому value [a] = 2 ^ (1-1) + 2 ^ (3-1) = 3 .

Теперь ваша цель - найти количество итенов с минимальным весом, таким, чтобы суммаего значения (1 + 2 + 4 + 8 + 16) = 31. Это в основном проблема ранца , хорошо известная проблема динамического программирования.Каждый предмет будет буквой, а ваш рюкзак имеет размер 5 (максимум).В этом размере вам нужно получить значение 31.

Что касается значения каждой буквы, вы можете просто выполнить предварительную обработку.

Answer 2

Вот как я это сделал.

def most_frequent(List):
   return max(set(List), key = List.count)

s1 = set(["a", "b", "c"])
s2 = set(["c", "d"])
s3 = set(["a", "g", "h"])
s4 = set(["d", "e", "f"])
s5 = set(["g", "k", "l"])
set_list = [s1, s2, s3, s4, s5]

return_set = []
while len(set_list) > 0:
   elements = []
   for s in set_list:
       for el in s:
           elements.append(el)
   element = most_frequent(elements)
   return_set.append(element)
   new_set_list = []
   for s in set_list:
       if element not in s:
           new_set_list.append(s)
   set_list = new_set_list
print(return_set)

Answer 3

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

Answer 4

Есть другой способ сделать это, как я только что узнал.По сути, каждый элемент является переменной bool, а каждый набор является набором ограничений OR.Каждый набор должен возвращать true с минимальным количеством элементов, установленным на true.Это оказывается очень легко решаемым с помощью линейного решателя, такого как z3.Просто установите сумму сумм true в каждом наборе в качестве переменной, которую нужно минимизировать, и вуаля.

Answer 5

Вы можете использовать itertools.combinations, чтобы выбрать все большее количество предметов из всех отдельных предметов и проверить, есть ли в выбранном наборе предметов хотя бы один предмет в каждом наборе в списке:

from itertools import count, combinations
r = [{'a', 'b', 'c'},
     {'c', 'd'},
     {'a', 'g', 'h'},
     {'d', 'e', 'f'},
     {'g', 'k', 'l'}]
all_items = set.union(*r)
print(next(set(picks) for size in count(1)
    for picks in combinations(all_items, size)
    if all(any(i in s for i in picks) for s in r)))

Это выводит: (Ваш пример ввода имеет более одного оптимального решения и выводит только одно из них.)

{'c', 'd', 'g'}

Если вы хотите все оптимальные решения, вы можете использовать itertools.groupby над выражением генератора выше сlen в качестве ключевой функции:

from itertools import groupby
list(next(groupby((set(picks) for size in count(1)
    for picks in combinations(all_items, size)
    if all(any(i in s for i in picks) for s in r)), len))[1])

Возвращает:

[{'f', 'c', 'g'},
 {'e', 'c', 'g'},
 {'a', 'd', 'g'},
 {'b', 'd', 'g'},
 {'c', 'd', 'g'},
 {'a', 'd', 'l'},
 {'a', 'd', 'k'}]