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