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