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
- Combinations