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

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