Dec 132017

BAG – a lisp implimentation of the BAG data structure. | |||
---|---|---|---|

File Name | File Size | Zip Size | Zip Type |

BAG.L | 5967 | 1533 | deflated |

BAG.TXT | 2835 | 1118 | deflated |

# Download File BAG.ZIP Here

## Contents of the BAG.TXT file

A Bag is a set which may contain duplicate elements.

Assume B = (a, b, a, c, b) and C = (a, b, c).

If B and C are sets, we may conclude that B = C; however,

if B and C are bags, then B != C. B and C are different as bags

because C contains only single instances of a and b, while B

contains two instances of each of these elements.

You are to write functions that manipulate bags using a property list

representation in which a bag has a property called Elements. Elements

is a list of ordered pairs; the first item in each pair is the value of

the bag element and the second is the number of occurrences of the value.

For example, the bag B above would have the list ((a 2) (b 2) (c 1)) as

the value of its element property.

Note: A property list can be associated with a variable using a command

PUTPROP and retrieved using a command GET. Here is an example:

(putprop 'Bag1 '((a 3) (b 1) (c 2)) 'Elements)

The above command causes the list to be Elements property of a variable

Bag1.

You are to implement the following functions:

(BagEqual B1 B2) is a predicate which is true if B1 and B2 have exactly

the same elements occurring the same number of times, and false otherwise.

(BagUnion B1 B2) is a function that returns a new bag containing the

elements of both B2 and B2. The number of times that an element occurs

in this new bag is the maximum of its occurrences in either B1 or B2. So,

if B1 = (a b c c b c a) and B2 = (a c b b b c), then (BagUnion B1 B2) =

(a a b b b c c c).

Note: The order in which the elements appear in the Union may be

different for your particular function.

(BagIntersection B1 B2) is a function that returns a new bag in which the

number of times that each element occurs is the minimum of its occurrence

in either bag. So, for B1 and B2 defined above, (BagIntersection B1 B2) =

(a b b c c).

Note: If an element occurs zero times, it should not be listed in

the property list representation of a bag.

(BagDifference B1 B2) is a function that returns a new bag. If a occurs n

times in B1 and m times in B2, then a occurs Max (0, n-m) times in the new

bag. So, for B1 and B2 defined above, (BagDifference B1 B2) = (a c).

(SubBag B1 B2) is a predicate that evaluates to true if and only if B1 is

contained in B2. For this to be the case, for all a in B1, if a occurs n

times in B1, it must occur n times in B2. Otherwise the predicate evaluates

to false.

(PrintBag B1) is a function that prints out the content of the bag. It

prints the name of the bag, followed by one line of output for each element

of the bag, giving its name and count. So, for B1 = (a b a a c d b),

(PrintBag B1) should print:

B1

(a 3)

(b 2)

(c 1)

(d 1)

Note: For the empty bag, print the name of the bag and one line

containing ().

Assume B = (a, b, a, c, b) and C = (a, b, c).

If B and C are sets, we may conclude that B = C; however,

if B and C are bags, then B != C. B and C are different as bags

because C contains only single instances of a and b, while B

contains two instances of each of these elements.

You are to write functions that manipulate bags using a property list

representation in which a bag has a property called Elements. Elements

is a list of ordered pairs; the first item in each pair is the value of

the bag element and the second is the number of occurrences of the value.

For example, the bag B above would have the list ((a 2) (b 2) (c 1)) as

the value of its element property.

Note: A property list can be associated with a variable using a command

PUTPROP and retrieved using a command GET. Here is an example:

(putprop 'Bag1 '((a 3) (b 1) (c 2)) 'Elements)

The above command causes the list to be Elements property of a variable

Bag1.

You are to implement the following functions:

(BagEqual B1 B2) is a predicate which is true if B1 and B2 have exactly

the same elements occurring the same number of times, and false otherwise.

(BagUnion B1 B2) is a function that returns a new bag containing the

elements of both B2 and B2. The number of times that an element occurs

in this new bag is the maximum of its occurrences in either B1 or B2. So,

if B1 = (a b c c b c a) and B2 = (a c b b b c), then (BagUnion B1 B2) =

(a a b b b c c c).

Note: The order in which the elements appear in the Union may be

different for your particular function.

(BagIntersection B1 B2) is a function that returns a new bag in which the

number of times that each element occurs is the minimum of its occurrence

in either bag. So, for B1 and B2 defined above, (BagIntersection B1 B2) =

(a b b c c).

Note: If an element occurs zero times, it should not be listed in

the property list representation of a bag.

(BagDifference B1 B2) is a function that returns a new bag. If a occurs n

times in B1 and m times in B2, then a occurs Max (0, n-m) times in the new

bag. So, for B1 and B2 defined above, (BagDifference B1 B2) = (a c).

(SubBag B1 B2) is a predicate that evaluates to true if and only if B1 is

contained in B2. For this to be the case, for all a in B1, if a occurs n

times in B1, it must occur n times in B2. Otherwise the predicate evaluates

to false.

(PrintBag B1) is a function that prints out the content of the bag. It

prints the name of the bag, followed by one line of output for each element

of the bag, giving its name and count. So, for B1 = (a b a a c d b),

(PrintBag B1) should print:

B1

(a 3)

(b 2)

(c 1)

(d 1)

Note: For the empty bag, print the name of the bag and one line

containing ().

December 13, 2017
Add comments