我想解决以下类型的一组最小的覆盖问题。所有名单只包含1和0。

I would like to solve a minimum set cover problem of the following sort. All the lists contain only 1s and 0s.

我说，一个List A 涵盖列表 B 如果你可以让 B 从 A 插入完全 X 符号。

I say that a list A covers a list B if you can make B from A by inserting exactly x symbols.

考虑1和长度的0所有2的n次方名单 N ，并设置 X = N / 3 。我会计算一组长度 2N / 3 ，涵盖所有这些名单中最小的。

Consider all 2^n lists of 1s and 0s of length n and set x = n/3. I would to compute a minimal set of lists of length 2n/3 that covers them all.

下面是一个天真的做法我已经开始。对于长度为每一个可能的名单 2N / 3 我创建了一个集合中的所有名单，我可以创建使用此功能（书面DSM）它。

Here is a naive approach I have started on. For every possible list of length 2n/3 I create a set of all lists I can create from it using this function (written by 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（产品（[0,1]，重复= N））。

在这种情况下，设置（all_fill（[1,1,1,1]，2）），集（all_fill（[0,0,0,0]，2）），设置（all_fill（[1,1,0,0]，2）），集（all_fill（[0,0,1,1]，2））就行了。

In this case, 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)) will do.

我的目的是要解决对的问题，N = 12 。我很高兴地使用外部库是否会帮助，我希望时间是指数在 N 在最坏的情况下。

My aim is to solve the problem for n = 12. I am happy to use external libraries if that will help and I expect the time to be exponential in n in the worst case.

推荐答案

我写了一个小程序，写一个整数程序被解决 CPLEX或其他MIP求解器。下面是n的解决方案= 12。

I’ve written a small program to write an integer program to be solved by CPLEX or another MIP solver. Below it is a solution for 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>