The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » Math Topics » discretemath

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Set Theory Problem
Replies: 1   Last Post: Jan 15, 2010 12:17 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 1
From: England
Registered: 5/6/09
Set Theory Problem
Posted: May 6, 2009 4:25 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


I need help with creating an algorithm to solve the problem below in the most efficient manner (efficiency in this case means low processing, not memory)

(Disclaimer: I studied discrete maths as part of my university course, but this was many years ago and I have forgotten most of the correct syntax. Sorry!)

Imagine we have

Set A (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
Set B (3,3,4,5,5,5,5,5,6,6,7,8,12)
Set C
Set C.A (1,2) = 10
Set C.B (1,4,3) = 15
Set C.C (3,4,5) = 20
Set C.D (3,3,4,5) = 25
Set C.E (5,6) = 10
Set C.F (5,5,6) = 10
Set C.G (3,3,4,5,5,5,5,5,6,6,7,8,12) = 5

B is a subset of A
C is a subset of A

I need to find
1) Which C are in B
2) What is the best combination of C. (Best means the biggest value i.e. C.A is worth 10, C.B is worth 15 etc)

When a C is found in B; B is to be reduced by C (e.g. if C.G is applied to B, there will nothing left in B)
A single instance of C can be applied to B a number of times (e.g. C.E above is in B twice)

Assume I have done 1 and the method is called GetApplicableSets(SetB) and the example above would return C.C, C.D, C.E, C.F, C.G

How do I do 2?

Date Subject Author
Read Set Theory Problem
Read Re: Set Theory Problem

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.