MathGroup Archive 2005

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

Search the Archive

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


  • Prev by Date: Re: FullSimplify again ...
  • Next by Date: Re: BlankSequence
  • Previous by thread: Re: pairs and subsets challenge
  • Next by thread: Re: pairs and subsets challenge