Re: Combinations

*To*: mathgroup at smc.vnet.net*Subject*: [mg15217] Re: [mg15181] Combinations*From*: Jurgen Tischer <jtischer at col2.telecom.com.co>*Date*: Tue, 22 Dec 1998 04:01:46 -0500*Organization*: Universidad del Valle*References*: <199812180710.CAA03901@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

Since the problem can be stated as a set cover problem (one covers the set of all t-subsets with the sets made out of the t-subsets of u-subsets), Daniel's approach is the standard one. And set cover problems are NP-hard. Since there is extra structure one can hope for doing a little bit better. I used the suggestion of Daniel, but refined it by selecting among the u-sets which cover a maximal number of the remaining sets one that has a maximal overlap with already chosen u-sets. (I found this condition by looking at lots of approximate solutions of the greedy algorithm.) Looks like it works better, but of course it's still a heuristic method without any proof of minimality. And it's slow, I checked it only for very small numbers. (The time it took me to write this little program shows how bad I am in that field.) In[1]:= <<DiscreteMath`Combinatorica` In[2]:= fu1[li_,ln_]:= With[{li1=Flatten[KSubsets[#,3]&/@li,1]},Length/@(Complement[#,li1]&/@ln)] In[3]:= fu2[elem_,li_]:=Length[Intersection[elem,li]] In[4]:= newElem[li_,ln2_,ln21_]:=Module[{li1=fu1[li,ln21], li2=Union[Flatten[li]],li3,m,elem}, li3=Extract[ln2,Position[li1,Max[li1]]]; m=Max[fu2[#,li2]&/@li3]; First[Select[li3,fu2[#,li2]==m&,1]]] In[5]:= totlen[li_,len1_]:=Length[Union[Flatten[KSubsets[#,len1]&/@li,1]]] In[6]:= minCover[lentotal_,len1_,len2_]:= Module[{ran=Range[lentotal],ln1,ln2,ln21,lenln1,li={Range[len2]}}, ln1=KSubsets[ran,len1]; lenln1=Length[ln1]; ln2=KSubsets[ran,len2]; ln21=KSubsets[#,len1]&/@ln2; While[totlen[li,len1]<lenln1,AppendTo[li,newElem[li,ln2,ln21]]]; li] In[7]:= minCover[12,3,6] Out[7]= {{1,2,3,4,5,6},{1,2,7,8,9,10},{3,4,7,8,11,12},{5,6,9,10,11,12},{1,2,3,9,11, 12},{1,4,5,7,10,11},{2,4,6,8,10,12},{3,5,6,7,8,9},{1,3,6,7,10,12},{1,4,5, 8,9,12},{2,3,5,8,10,11},{2,4,6,7,9,11},{1,3,6,8,9,11},{2,3,5,7,9,12},{1,2, 3,4,9,10}} Jurgen edsferr at uol.com.br wrote: > > Hello ! > > I'm not sure if what I have is a difficult or an easy problem... > > Let L be this list : L={1,2,3,4,..,n} Let LNT be a list of all the > combinations of the n elements in list L when you take t elements. We > get LNT using KSubsets[L,t] Let u be an integer so t < u < n > Let LNU be a list of all the combinations of the n elements in list L > when you take u elements. We get LNU using KSubsets[L,u] > > Let's take one element of LNU: Due to the fact of t < u , this element > of LNU "contains" exactly u!/(t!(u-y)!) elements of LNT when you take t > elements of it. > > The question is: How can i get the shortest list of elements of LNU so > we can "have" all the elements of LNT "inside" of this list ? > > Thanks !!!!!!!!!!! > > -----------== Posted via Deja News, The Discussion Network ==---------- > http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own

**References**:**Combinations***From:*edsferr@uol.com.br