20-ECES-228-001 Data Structures Fall 2007

Homework Assignment Number 4

Hamming's Problem and Priority Queues

Due: October 19, 2007
Submit source code implementing solution to Hamming's problem to xxxxx@email.uc.edu

Rationale:

    This problem is a simple but non-trivial example of the use of priority queues. A great challenge would be to solve the problem efficiently without priority queues. A simple guess and check scheme would solve the problem but would be too slow to be useful and is therefore not an acceptable solution.

Homework Problem:

    Write a program to solve Hamming's Problem. This problem and an outline of the code you can write are as follows:

Hamming's Problem Extended:

    Given a list p of prime numbers in increasing order. The Hamming Sequence Sp is an infinitely long list of integers, in increasing order, such that integer x is a member of Sp if and only if its prime factors (excluding 1) are all in the list p. Write a C++ program which takes a prime list p and a number n as input and prints the first n numbers of Sp.

Example:

    Assume the input has n equal to 13 and p equal to the following:

    3, 5, 11

The output is the the following list of 13 numbers:

3, 5, 9, 11, 15, 25, 27, 33, 45, 55, 75, 81, 99

Review of Priority Queues and Heaps:

    A priority queue is a container of objects, all having some value. As usual for container classes, objects may be inserted and removed from a priority queue, but a priority queue differs from a queue in that the highest (or lowest) valued object currently in the priority queue is removed. Code implementing a priority queue is found in pqueue.cc and pqueue.h. A description of this code is found in homework number 2.

Conceptual Description of the Solution:

    A simple guess and check solution is not acceptable since it usually takes too long to run. The following concept is potentially very efficient:

Let ham(p) denote a function that produces a list of integers representing the solution to the instance of Hamming's problem given by the list of primes p. Let lst denote a list of integers in increasing order. Let mult(lst,m) denote a function that multiplies all integers in lst by m and returns the modified list. Let first(lst) denote a function that returns the first integer in lst. Let rest(lst) denote a function that returns a list of integers in increasing order containing all the integers of lst except with first(lst) removed. Let concat(m,lst) denote a function that returns the list created by adding the number m to the front of the list lst. Let merge(lst1,lst2) denote a function that returns an increasing list of all the integers in increasing integer lists lst1 and lst2. Then the solution may be described as follows:

   List *ham(List *p) {
      if (p->empty()) return NULL;
      else
         return concat(first(p), merge(mult(ham(p),first(p)),ham(rest(p))));
   }

A simple illustration of this is as follows. The hamming output for the input list 3, 5, 11 may be viewed like this

                                     3*(3, 5, 9, 11, 15, 25, 27, 33, ...)
  3 concatenated with the merge of <
                                     5, 11, 55, ...

Why can't we just use recursive C++ code that looks pretty much like the code above for ham to solve this problem? Because the recursion will attempt to solve ham(p) over and over (ham(p) calls ham(p) which calls ham(p) and so on until there is no space left on the computer). The recursion is unable to ask the question whether first(mult(ham(p),first(p))) is greater or smaller than first(ham(rest(p))). If it could, it would not attempt to evaluate mult(ham(p),first(p)) unless its first element it is greater than the first element of ham(rest(p)). In that case, ham(p) would not be called indefinitely.

So, how does a priority queue help with this? The priority queue allows us to suspend the recursive invocation of the two arguments of the merge allowing the first elements of the lists represented by those two arguments to be compared. Then the invocation proceeds with the list containing the least first element.

So, what gets enqueued? Enqueued objects need to contain all the information that is needed to reconstruct the corresponding list. For example, what is need to reconstruct the call ham(rest(p))? Just the list p minus the first number. To reconstruct the call mult(ham(p),first(p)) we need to remember p and the fact that all the elements of ham(p) get multiplied by first(p). So, generally, we need to remember just two items for total reconstruction: a prime list and a multiplier (or whether a multiplier should be applied).

So, what enqueued object should be removed? This is a little sticky because in addition to the information above, we need also to maintain information about the multiplications that have already taken place up to this point. It is probably easiest, then, to save this information as the actual number that is the first number in the list represented by the enqueued object.

Since you are undoubtedly lost at this point, let's look at the following example. Suppose the information described above is represented as the triple

    <first_element:multiplier:prime_list>
Then, the original problem, assuming the input prime list is {3,5,11}, is represented by the triple:
    <3:1:{3,5,11}> 
According to the algorithm given above, the first number of the output list is 3 which is conveniently found to be the first element of the triple representing the original problem. The remaining numbers are obtained as a result of the merge of two lists. These may be represented as triples as follows:
    <9:3:{3,5,11}>  representing "mult(ham(p),first(p))"
    <5:1:{5,11}>    representing "ham(rest(p))"
These are enqueued in a priority queue where "value" is determined by the first element of each enqueued triple. Then using remove on the priority queue will return the triple <5:1:{5,11}>, leaving the triple <9:3:{3,5,11}> alone in the priority queue. The returned triple contains the next number that should be output, namely the first element of the triple which is 5. But the remainder of the list represented by the removed object is determined by the merge of two lists represented by the triples
    <25:5:{5,11}>  and   <11:1:{11}>
Both triples should be enqueued. At this point the priority queue contains (showing the "order" based on value of first triple element):
    <9:3:{3,5,11}>, <11:1:{11}>, and <25:5:{5,11}>
The next object removed from the priority queue is the one of lowest value which is <9:3:{3,5,11}>. The first number of the list this represents is 9. The remainder of the list is represented by the triples:
    <27:9:{3,5,11}>  and   <15:3:{5,11}>
since all numbers must be multiplied by 3, according to the representation just removed from the priority queue. These two triples should be enqueued leaving the contents of the priority queue as:
    <11:1:{11}>, <15:3:{5,11}>, <25:5:{5,11}>, and <27:9:{3,5,11}>
Applying remove to the priority queue provides the next output number, which is 11, and causes <121:11:{11}> to be enqueued (no empty lists should be enqueued hence the second triple, namely <?:1:Φ>, is not enqueued). At this point the priority queue contains:
    <15:3:{5,11}>, <25:5:{5,11}>, <27:9:{3,5,11}>, and <121:11:{11}>
Removing <15:3:{5,11}> from the priority queue results in outputting 15 and a queue containing:
    <25:5:{5,11}>, <27:9:{3,5,11}>, <33:3:{11}>, <75:15:{5,11}>, and <121:11:{11}>
Removing <25:5:{5,11}> from the priority queue results in outputting 25 and a queue containing:
    <27:9:{3,5,11}>, <33:3:{11}>, <55:5:{11}>, <75:15:{5,11}>, <121:11:{11}>, and <125:25:{5,11}>
Removing <27:9:{3,5,11}> from the priority queue results in outputting 27 and a queue containing:
    <33:3:{11}>, <45:9:{5,11}>, <55:5:{11}>, <75:15:{5,11}>, <81:27:{3,5,11}>, <121:11:{11}>, and <125:25:{5,11}>
(notice the 45 element made it into the queue with little time to spare). Removing <33:3:{11}> from the priority queue results in outputting 33 and a queue containing:
    <45:9:{5,11}>, <55:5:{11}>, <75:15:{5,11}>, <81:27:{3,5,11}>, <121:11:{11}>, <125:25:{5,11}>, and <363:33:{11}>, 
By now you probably see the pattern. Namely, enqueue the triple representing the input, then repeat the following indefinitely: remove a triple from the priority queue; output its first element; create a new triple from the removed triple (where the second element of the new triple is the product of the first number of the list given by the third element of the removed triple and the number given by the second element of the removed triple, the third element of the new triple is the same as that of the removed triple, and the first element of the new triple is the product of its second element and the first number of its third element) and enqueue it; if the third element of the removed triple contains two or more numbers, create a second new triple (with second element the same as that of the removed triple, with third element that same except with the first number removed, and with first element equal to the product of the second element and the first number of the third element) and enqueue it.

Your assignment is to implement a solution to Hamming's problem which relies on the PQueue class in the manner outlined above.

A Clever Solution to Hamming's Problem:

    A more interesting, although not more efficient, solution to Hamming's problem makes use of the properties of C++ classes to suspend recursion. The suspension is effected by object creation as in:
    Hamming *ham = new Hamming(primes);
Resumption of recursion is effected by invocation of a particular method of the Hamming class. The result is more readable to some people (such as myself). The student is invited to see hamming.cc