MathGroup Archive 2005

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

Search the Archive

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


  • Prev by Date: Re: Obtaining the output from the line above.
  • Next by Date: Re: Manipulating a matrix
  • Previous by thread: Re: pairs and subsets challenge
  • Next by thread: Re: pairs and subsets challenge