Dec 132017
 
BAG - a lisp implimentation of the BAG data structure.
File BAG.ZIP from The Programmer’s Corner in
Category Miscellaneous Language Source Code
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 ().


 December 13, 2017  Add comments

Leave a Reply