MathGroup Archive 2005

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

Search the Archive

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.


  • Prev by Date: Re: FullSimplify again ...
  • Next by Date: Mathematica: Assistance requested.
  • Previous by thread: speed up numerical integration
  • Next by thread: Mathematica: Assistance requested.