Минимальное обложка

Question

Я хотел бы решить проблему с минимальным набором обложек следующего вида. Все списки содержат только 1 и 0.

Я говорю, что список A охватывает список B, если вы можете сделать B из A путем вставки точно x символов.

Просмотреть все 2^n списки из 1s и 0s длины n и установить x = n/3. Я бы вычислил минимальный набор списков длины 2n/3, который охватывает их все.

Вот наивный подход, который я начал. Для каждого возможного списка длины 2n/3 Создаю набор всех списков, которые я могу создать из него, используя эту функцию (написанную DSM).

from itertools import product, combinations 

def all_fill(source, num): 
    output_len = len(source) + num 
    for where in combinations(range(output_len), len(source)): 
     # start with every possibility 
     poss = [[0,1]] * output_len 
     # impose the source list 
     for w, s in zip(where, source): 
      poss[w] = [s] 
     # yield every remaining possibility 
     for tup in product(*poss): 
      yield tup 

Я затем создать набор множеств следующим использованием n = 6 в качестве примера.

n = 6 
shortn = 2*n/3 
x = n/3 
coversets=set() 
for seq in product([0,1], repeat = shortn): 
    coversets.add(frozenset(all_fill(seq,x))) 

Я хотел бы найти минимальный набор множеств из coversets, объединение которых allset = set(product([0,1], repeat=n)).

В этом случае set(all_fill([1,1,1,1],2)), set(all_fill([0,0,0,0],2)), set(all_fill([1,1,0,0],2)), set(all_fill([0,0,1,1],2)) сделаю.

Моя цель - решить проблему для n = 12. Я рад использовать внешние библиотеки, если это поможет, и я ожидаю, что время будет экспоненциальным в n в худшем случае.

Answer 1

Я написал небольшую программу для записи целочисленной программы, которая должна быть решена CPLEX или другим решателем MIP. Ниже это решение для n = 12.

---

from collections import defaultdict 
from itertools import product, combinations 

def all_fill(source, num): 
    output_len = (len(source) + num) 
    for where in combinations(range(output_len), len(source)): 
     poss = ([[0, 1]] * output_len) 
     for (w, s) in zip(where, source): 
      poss[w] = [s] 
     for tup in product(*poss): 
      (yield tup) 

def variable_name(seq): 
    return ('x' + ''.join((str(s) for s in seq))) 
n = 12 
shortn = ((2 * n) // 3) 
x = (n // 3) 
all_seqs = list(product([0, 1], repeat=shortn)) 
hit_sets = defaultdict(set) 
for seq in all_seqs: 
    for fill in all_fill(seq, x): 
     hit_sets[fill].add(seq) 
print('Minimize') 
print(' + '.join((variable_name(seq) for seq in all_seqs))) 
print('Subject To') 
for (fill, seqs) in hit_sets.items(): 
    print(' + '.join((variable_name(seq) for seq in seqs)), '>=', 1) 
print('Binary') 
for seq in all_seqs: 
    print(variable_name(seq)) 
print('End') 

---

MIP - Integer optimal solution: Objective = 1.0000000000e+01 
Solution time = 7.66 sec. Iterations = 47411 Nodes = 337 

CPLEX> Incumbent solution 
Variable Name   Solution Value 
x00000000      1.000000 
x00000111      1.000000 
x00011110      1.000000 
x00111011      1.000000 
x10110001      1.000000 
x11000100      1.000000 
x11001110      1.000000 
x11100001      1.000000 
x11111000      1.000000 
x11111111      1.000000 
All other variables matching '*' are 0. 
CPLEX>