matlab - Algorithm challenge to merge sets -

given n sets of numbers. each set contains numbers 1 100. how select sets merge longest set under special rule, 2 non-overlapping sets can merge. [1,2,3] can merge [4,5] not [3,4]. efficient algorithm merge longest set.

my first attempt form n n matrix. each row/column represents set. entry(i,j) equals 1 if 2 sets overlap, entry(i,i) stores length of set i. questions becomes can perform row , column operations @ same time create diagonal sub-matrix on top left corner trace large possible.

however, got stuck in how efficiently perform row , column operations form such diagonal sub-matrix on top left corner.

as pointed out in comments (maximum coverage problem) have np-hart problem. luckily, matlab offers solvers integer linear programming.

so try reduce problem form:

min f*x subject ax<=b , 0<=x 

there n sets, can encode set vector of 0s , 1s. example (1,1,1,0,0,...) represent {1,2,3} , (0,0,1,1,0,0...) - {3,4}.

every column of a represents set. a(i,j)=1 means i-th element in j-th set, a(i,j)=0 means i-th element not in j-th set.

now, x represents sets select: if x_j=1 set j selected, if x_j=0 - not selected!

as every element must @ in 1 set, choose b=(1, 1, 1, ..., 1): if take 2 sets contain i-th element, i-th element of (ax) @ least 2.

the question left f? try maximize number of elements in union, choose f_j=-|set_j| (minus owing min<->max conversion), |set_j| - number of elements in j-th set.

putting in matlab get:

f=-sum(a) xopt=intlinprog(f.',1:n,a,ones(m,1),[],[],zeros(n,1),ones(n,1)) 

• f.' - cost function column
• 1:n - n elements of x integers
• a - encodes n sets
• ones(m,1) - b=(1,1,1...), there m=100 elements
• [],[] - there no constrains of form aeq*x=beq
• zeros(n,1), 0<=x must hold
• ones(n,1), x<=1 follows others constrains, maybe solver little bit