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.