Re: pairs and subsets challenge
- To: mathgroup at smc.vnet.net
- Subject: [mg59215] Re: pairs and subsets challenge
- From: Daniel Reeves <dreeves at umich.edu>
- Date: Tue, 2 Aug 2005 00:42:35 -0400 (EDT)
- References: <dchnkq$7pe$1@smc.vnet.net> <42EE4014.3050607@dordos.net>
- Sender: owner-wri-mathgroup at wolfram.com
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}}
Thanks Peter.
Daniel
ps, I'm suspecting this problem is Hard (in the NP sense).
--- \/ FROM Peter Pein AT 05.08.01 17:30 (Today) \/ ---
> Daniel Reeves schrieb:
> > 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"
"If you can't beat your computer at chess, try kickboxing"
-- Submitted on 2001.08.09 by Flavia Ribeiro