MathGroup Archive 1998

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

Search the Archive

Re: Combinations

  • To: mathgroup at
  • Subject: [mg15217] Re: [mg15181] Combinations
  • From: Jurgen Tischer <jtischer at>
  • Date: Tue, 22 Dec 1998 04:01:46 -0500
  • Organization: Universidad del Valle
  • References: <>
  • Sender: owner-wri-mathgroup at

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_]:=

In[3]:= fu2[elem_,li_]:=Length[Intersection[elem,li]]

In[4]:= newElem[li_,ln2_,ln21_]:=Module[{li1=fu1[li,ln21],


In[6]:= minCover[lentotal_,len1_,len2_]:=

In[7]:= minCover[12,3,6]



edsferr at 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 ==----------
>       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