Re: pairs and subsets challenge
- To: mathgroup at smc.vnet.net
- Subject: [mg59348] Re: pairs and subsets challenge
- From: Bill Rowe <readnewsciv at earthlink.net>
- Date: Sat, 6 Aug 2005 01:29:57 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
On 8/4/05 at 2:08 AM, dreeves at umich.edu (Daniel Reeves) wrote: >{2,3,4,5} can't be in the output because one of its pairs ({2,5}) >is not in P. Does that clarify? >I'm pretty confident now that {{3,4,5}, {1,2,3,4}} is the correct >output. I had not carefully read your conditions and did not realize P specified at the start of the problem. For your particular example. >>>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}}; The following works: << "DiscreteMath`"; excluded = Complement[KSubsets[Range[5], 2], P]; sol = {Complement[Range[5], First /@ excluded], Complement[Range[5], Last /@ excluded]} {{3, 4, 5}, {1, 2, 3, 4}} Clealy, by construction, neither of these subsets can have pairs in the excluded set. Additionally, any other subset that does not have pairs in the exluded set must be a subset of one of these. But I haven't determined whether this method works in general. -- To reply via email subtract one hundred and four