Replies by Julius Kavay for InterSystems Developer Community

Since you want the smallest possible number of sets that cover the maximum number of elements, one of the simplest solutions (from a programming point of view) is to check all possible combinations of K out of N sets.

However, keep in mind that combinations grow (very) quickly. If your N tends to leave the single-digit range, you may need to resort to linear programming methods.

Some values for all combinations (K out of N) to see, how they grow:
N : 1 2 3 4 5 10 15 20 25 50
cnt: 1 3 7 15 31 1,023 32,767 1,048,575 33,554,431 1,125,899,906,842,623

Class DC.MaxCoverage Extends %RegisteredObject
{

ClassMethod Test(case = 0)
{
	if case=4 {
		set list($i(list))="1,2,3"
		set list($i(list))=""
		set list($i(list))="1,2,3"
	}
	elseif case=3 {
		set list($i(list))="1,2,3"
		set list($i(list))="4,5,6"
		set list($i(list))="1,2,3"
		
	} elseif case=2 {
		set list($i(list))="1,2,3"
		set list($i(list))="7,8,9"
		set list($i(list))="11,12,13,14,15"
		set list($i(list))="2,8,12"
		set list($i(list))="15,16,17"
		set list($i(list))="12,17,19,21,22,23"
		set list($i(list))="11,21,31,32,33"
		set list($i(list))="34,35,36"
		
	} elseif case=1 {
		set list($i(list))="1,2,3,4"
		set list($i(list))="5,6,7,8,9,10,11,12"
		set list($i(list))="2,3,4,5,6,7"
		
	} else { // the original testcase
		set list($i(list))="3,5,6,7,9"
		set list($i(list))="1,2,6,9"
		set list($i(list))="5,8,9"
		set list($i(list))="2,4,6,8"
		set list($i(list))="4,7,9"
	}
	
	quit ..MinMax(.list)
}

/// minimum number of sets with maximum number of coverage
/// 
ClassMethod MinMax(ByRef list)
{
	// I assume, all numbers are
	// a) integers and greater then 0 (else map the numbers to integers in the toBits() method)
	// b) and all sets have less then ca. 262100 elements
	// 
	set N=list
	for i=1:1:N s set(i)=..toBits(list(i))	// convert each list into a bitstring
	
	set max=0, min=N, lst=""				// max=covered numbers, min=required sets, lst=list of combinations
	
	for k=1:1:N {									// compute all (k out of n) combinations for each k
		set s=0, i(0)=0								// --+ compute k out of n
1		set s=s+1, i(s)=i(s-1), e(s)=N-k+s			//   |
2		for i(s)=i(s)+1:1:e(s) goto 1:s<k do chk	//   | check a particular combination
3		set s=s-1 if s goto 2:i(s)<e(s),3			// --+
	}
	quit min_" set(s) covers "_max_" elements with sets: "_lst	// return the result	
	
chk	set c=i(1),v=set(i(1))									// take the first set
	for i=2:1:s s c=c_","_i(i), v=$bitlogic(v|set(i(i)))	// OR it with the next
	set v=$bitcount(v,1)
	
	if v>max { set max=v,min=s,lst=c }
	elseif v=max,s<min { set min=s,lst=c }
	elseif v=max,s=min { s lst=lst_" or "_c }
}

/// convert a list of numbers into bitstring, i.e.: 1,2,4 --> 1101
/// 
ClassMethod toBits(x)
{
	set b=""
	for i=1:1:$l(x,",")-(x="") set $bit(b,$p(x,",",i))=1
	quit b
}

/// Sum of all combinations of N elements
/// 
ClassMethod AllComb(N)
{
	s s=0
	f k=1:1:N s s=s+..Comb(k,N)
	q s
}

/// Count of combinations of K elements out of N elements
/// 
ClassMethod Comb(k, n)
{
	s c=1
	f k=1:1:k s c=c/k*n, n=n-1
	q c
}

}

Tests


USER>for i=0:1:4 write ##class(DC.MaxCoverage).Test(i),!
3 set(s) covers 9 elements with sets: 1,2,4
2 set(s) covers 12 elements with sets: 1,2
7 set(s) covers 23 elements with sets: 1,2,3,5,6,7,8
2 set(s) covers 6 elements with sets: 1,2 or 2,3
1 set(s) covers 3 elements with sets: 1 or 3

USER>