pairs and subsets challenge
- To: mathgroup at smc.vnet.net
- Subject: [mg59155] pairs and subsets challenge
- From: Daniel Reeves <dreeves at umich.edu>
- Date: Sun, 31 Jul 2005 01:30:33 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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!)
--
http://ai.eecs.umich.edu/people/dreeves - - google://"Daniel Reeves"
Optimist: The glass is half full.
Pessimist: The glass is half empty.
Engineer: The glass is too big.