Re: Combinations
- To: mathgroup at smc.vnet.net
- Subject: [mg15185] Re: Combinations
- From: Daniel Lichtblau <danl>
- Date: Fri, 18 Dec 1998 23:20:26 -0500
- Organization: Wolfram Research, Inc.
- References: <75cv8v$3s4@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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
A reasonable approach for getting a "short" such list might be to employ
a greedy algorithm. I have no idea whether this will produce a shortest
list, or, if, not, by how much it might miss. The idea is to generate
the length-t sets and the length-u sets. Choose any of the latter, say
the first, to be in your result list, and remove it from further
consideration in the u-sets. Remove from the t-sets all those contained
in this selected u-set. Now loop over all remaining u-sets, choose one
that removes the maximal number of remaining t-sets. Remove it from the
u-sets and add it to your result. Remove from the t-sets all of its
length-t subsets that are still there. Continue to do this until all
t-sets are gone.
Offhand it sounds like a hard problem, but I really do not know much
about this. If you do not get an answer you like, maybe try it on the
news groups sci.math, sci.math.symbolic, and perhaps sci.math.research.
This last is moderated, but I imagine the question would be posted.
Daniel Lichtblau
Wolfram Research