Re: pairs and subsets challenge
- To: mathgroup at smc.vnet.net
- Subject: [mg59286] Re: pairs and subsets challenge
- From: Daniel Reeves <dreeves at umich.edu>
- Date: Thu, 4 Aug 2005 02:08:14 -0400 (EDT)
- References: <dcpm03$6sc$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
{2,3,4,5} can't be in the output because one of its pairs ({2,5}) is not
in P. Does that clarify?
I'm pretty confident now that {{3,4,5}, {1,2,3,4}} is the correct output.
--- \/ FROM Bill Rowe AT 05.08.03 05:50 (Today) \/ ---
> On 8/2/05 at 12:42 AM, dreeves at umich.edu (Daniel Reeves) wrote:
>
> >You're right! That was my mistake (did the example by hand,
> >stupidly). Corrected output: (um, still by hand)
>
> >{{3,4,5}, {1,2,3,4}}
>
> Your description is still confusing. Given the starting set {1,2,3,4,5}
> why wouldn't {{1,2,3}, {1,2,4,5}} or {{1,2,3},{2,3,4,5}} be possible
> solutions? Or even better, why would not the 5 length 4 subsets given by
> KSubsets[Range@5, 4] be the set of solutions? None of these are subsets
> of each other and any possible shorter length subset must be a subset of
> one of these.
> > Here's an interesting problem:
> >
> > Given a set N = {1,...,n}.
> > And given a set P of pairs from N, ie, a subset of KSubsets[N,2].
> > List each _maximal_ subset X of N such that KSubsets[X,2] is a
> > subset of P.
> > Maximal means if X is listed, don't list any subsets of X.
> >
> > Brute force solutions are not hard to write. This should work for n
> > up to 40 and |P| around 500.
> >
> > Simple example:
> >
> > N = {1,2,3,4,5};
> > P = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{3,5},{4,5}};
> >
> > output:
> >
> > {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{3,5},{4,5},
> > {3,4,5}, {1,2,3,4}}
> >
> >
> > (no prize this time but I think it'll be fun!)
> >
> I do not understand the task
> " Maximal means if X is listed, don't list any subsets of X."
> " output:
> {{1,2},... {1,2,3,4}}"
>
> but {1,2} is a subset of {1,2,3,4}
--
http://ai.eecs.umich.edu/people/dreeves - - google://"Daniel Reeves"