Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1998
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: combinations of n objects 2 at a time
  • Next by Date: Re: Including Mathematica notebooks in LaTeX
  • Previous by thread: Combinations
  • Next by thread: Re: Combinations