Computer Representation of Sets

Computer Representation of Sets

• There are various ways to represent sets using a computer, and one method is to store elements in an unordered fashion.
• However, this method is inefficient for computing the union, intersection, or difference of two sets, as it requires a large amount of searching for elements.
• A more efficient method is to store elements using an arbitrary ordering of the elements of the universal set.

Bit String Representation

• Represent a subset A of U with a bit string of length n, where the i-th bit in the string is 1 if aj belongs to A and 0 if aj does not belong to A.
• Example: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order.
• The bit string for the set of odd integers in U is 1 0 1 0 1 0 1 0 1 0.
• The bit string for the set of all even integers in U is 0 1 0 1 0 1 0 1 0 1.
• The bit string for the set of all integers in U that do not exceed 5 is 1 1 1 1 1 0 0 0 0 0.

Operations on Bit Strings

• To obtain the bit string for the union and intersection of two sets, perform bitwise Boolean operations on the bit strings.
• Union: OR operation
• Intersection: AND operation
• Example: Find the bit string for the union and intersection of two sets A1 = {1, 3, 5, 7, 9} and A2 = {1, 2, 3, 4, 5}.
• A1 ∪ A2 = 1 1 1 1 1 0 1 0 1 0
• A1 ∩ A2 = 1 0 1 0 1 0 0 0 0 0

Multisets

• Multisets are unordered collections of elements where an element can occur as a member more than once.
• The notation {m1.a1, m2.a2, ..., mr.ar} denotes the multiset with element a1 occurring m1 times, element a2 occurring m2 times, and so on.
• The union of the multisets P and Q is the multiset where the multiplicity of an element is the maximum of its multiplicities in P and Q.
• The intersection of P and Q is the multiset where the multiplicity of an element is the minimum of its multiplicities in P and Q.
• The difference of P and Q is the multiset where the multiplicity of an element is the multiplicity of the element in P less its multiplicity in Q unless this difference is negative, in which case the multiplicity is 0.
• The sum of P and Q is the multiset where the multiplicity of an element is the sum of multiplicities in P and Q.

Operations on Multisets

• The union, intersection, and difference of P and Q are denoted by P U Q, P ∩ Q, and P - Q, respectively.
• The sum of P and Q is denoted by P + Q.
• Example: Let A = {3.a, 2.b, 1.c} and B = {2.a, 3.b, 4.d}, find A ∪ B, A ∩ B, A + B, A - B, B - A.
• A ∪ B = {3.a, 3.b, 1.c, 4.d}
• A ∩ B = {2.a, 2.b}
• A + B = {5.a, 5.b, 1.c, 4.d}
• A - B = {1.a, 1.c}
• B - A = {1.b, 4.d}