How to combine two generators in a non-trivial way.

Question

Hi, I have a generator which produces all positive integers that are powers of 2, and another which produces all integers that are powers of 3. I now need to use those to produce integers of the form 2^i*3^j where i,j >=0,0 in the increasing order.

The point of using generators is to reduce memory consumption, I think. I have been trying to do this for a while now to no avail. Please help out.

Answer 1

At least if I understand your question, you just need to merge the results from the two generators:

1. Generate an output from each generator
2. Produce the smaller of the two as the next output
3. Generate the next output from that generator
4. Go back to Step 2

If the two generators produce equal values, produce that as the output, and generate the next value from each generator.

Note that although it's typically used for sorting existing data instead of generating new data, this is similar to the merge used in a normal merge sort, with the exception that I've assumed you don't want duplicates, where a merge sort normally retains duplicates.

Edit: Thanks to lpthnc, I've reread the question, and I think he's right -- I misread the original question. To get the correct output, you'd need to create a third generator and produces the multiples of (in this case) six, and use a three-way merge between that result set and those from the other two generators.

I haven't played with it much, but I believe the Lazy language level (or lazy module) in recent iterations of PLT Scheme would let you write your code to generate the entire infinite sequence, which would theoretically use infinite time and memory, but only evaluate a finite subset of that as needed.

Answer 2

The simple solution w/o any examples is creating a new one.

for (i = 0; i < X; i++)
{
 if (i%2 or i%3)
 {
  cout << i
 }
}

edit: X is how long you want to run it say you want output 0-100 put 100.

int counter = 1000;
bool done = false;
while(!done)
{
 if (i%2 or i%3)
 {
  cout << i;
  counter--;
  if(counter <= 1)
   {
     done = true;
   }
 }
i++;
}

It's a little messy but should work.

edit: The counter should end at 1 or it will give you 1001 items.

Answer 3

Just merge the two ordered lists a la

(define merge
  (lambda (pred ls1 ls2)
    (cond
      [(null? ls1) ls2]
      [(null? ls2) ls1]
      [(pred (car ls1) (car ls2))
       (cons (car ls1) (merge pred (cdr ls1) ls2))]
      [else (cons (car ls2) (merge pred ls1 (cdr ls2)))])))

lifted from here.

Answer 4

This is pretty easy in Haskell:

merge as bs =
  case (as, bs) of
    ([], _) -> bs
    (_, []) -> as
    ((a:as'), (b:bs')) ->
      if a <= b
        then a : (merge as' bs)
        else b : (merge as bs')
rmDups as =
  case as of
    [] -> []
    [a] -> [a]
    (a:bs@(b:_)) ->
      if a == b
        then rmDups bs
        else a:(rmDups bs)
take 25 $ rmDups $ merge (map (2^) [1..]) (map (3^) [1..])

yields the following:

[2,3,4,8,9,16,27,32,64,81,128,243,256,512,729,1024,2048,2187,4096,6561,8192,16384,19683,32768,59049]

though I imagine there's a more elegant way to do it...

Answer 5

I don't know much about generators, however I can propose a solution based on streams (lazily constructed, possibly infinite lists), which are somewhat similar.

My approach would be to create a stream whose "state" itself would be a stream of streams.

The individual, inner streams of numbers, let's call them the 3-streams, would represent lists of the successive powers of 3, starting with 1, multiplied by a given power of two. We can then assemble an infinity of such 3-streams, one for each successive power of 2, starting with 1. Let's call this the 2-stream.

The initial state, in ascii-art, is this:

---------------------- --- -- -
| The 2-stream ...
--|----|----|----|---- --- -- -
  V    V    V    V
 |1| | 2| | 4| | 8|
 |3| | 6| |12| |24| ...
 |9| |18| |36| |72|         The 3-streams
  :    :    :    :

Now, we're going to manipulate this so that at any moment, the 3-streams will be ordered within the 2-stream with regards to their first elements. As a consequence the next smallest generated number will always be the first element of the first 3-stream.

So, to get the next number in the sequence you wish to obtain, we're going to pull out the first 3-stream, pull out its first element (which is the number we're interested in), and then re-insert the 3-stream in the 2-stream at a position determined by its new first element. The new state after the first number (1) has been extracted would be:

---------------------- --- -- -
| The 2-stream ...
---|----|----|----|---- --- -- -
   V    V    V    V
 | 2| | 3| | 4| | 8|
 | 6| | 9| |12| |24| ...
 |18| |27| |36| |72|         The 3-streams
  :    :    :    :

Note that this method does not depend on 2^i, 3^j or multiplication specifically (just on 2^i * 3^j being monotonically increasing with i and j). I have posted another answer which does, and is much more simple and fast as a result. don't trust me: it has nothing to do with the math

Below is an example implementation, using SRFI-41 streams:

(require srfi/41)

; Geometric sequence with initial value 'init', and ratio 'r'
(define (make-geoseq init r)
  (stream-cons
    init
    (make-geoseq (* r init) r)))

; Your power generators
(define pow2 (make-geoseq 1 2))
(define pow3 (make-geoseq 1 3))

; Construct a 3-stream from the pow3 sequence
(define (make-3stream mult)
  (stream-map (lambda (x) (* mult x)) pow3))

; Construct the (initial) 2-stream from the pow2 sequence
(define initial-2stream
  (stream-map make-3stream pow2))

; Insert a modified 3-stream into the given 2-stream, at the right position
(define (insert two-stream three-stream)
  (if (< (stream-car three-stream)
         (stream-car (stream-car two-stream)))
    ; we have the smallest 3-stream, put it at the front
    (stream-cons
      three-stream
      two-stream) 
    ; otherwise, recurse
    (stream-cons
      (stream-car two-stream)
      (insert (stream-cdr two-stream) three-stream))))

; Construct a 2^n * 3^p stream with the given 2-stream as its "state"
(define (make-the-stream current-2stream)
  (let*
    ; pull out the first 3-stream
    ((first-3s (stream-car current-2stream))
     (other-3s (stream-cdr current-2stream))
     ; use its first element as our next value
     (next-val (stream-car first-3s))
     ; reinsert its tail into the 2-stream's tail
     (next-2s (insert other-3s (stream-cdr first-3s))))

    ; and use the resulting 2-stream to construct the (outer) stream's tail
    (stream-cons
      next-val
      (make-the-stream next-2s))))

; Now, we can construct the stream we want
(define the-stream (make-the-stream initial-2stream))

Using plt-scheme (on my rather crappy hardware):

$ mzscheme -f pow23.scm -e '(display (stream->list (stream-take 20 the-stream)))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f pow23.scm -e '(display (stream-ref the-stream 10000))'
161968247347450370721577384417107686788864605658546176
real    0m12.550s
user    0m11.005s
sys     0m0.340s

Implementing this with generators could be done I guess, but the tricky part would be implementing (insert). You could do so by composing generators, but you would end up adding one "layer" every time a number is pulled, whereas a stream created with (insert) shares its tail with the original one (the "layers" eventually merge).

Answer 6

Using a self-reading stream

You can solve this using a self-read stream:

   -----------        -----------
   |  pow 2  |------->|         |
   -----------        |         |
                      |  merge  |-------+------------>
   -----------        |         |       |
.->|   x 3   |------->|         |       |
|  -----------        -----------       |
\_______________________________________/

The first stream produces the powers of two, while the second one ensures all the generated numbers are multiplied by 3 and reinjected into the output. The merge operator ensures that the output is sorted.

Note that we must "seed" the output stream with 1, or the first element will try to produce itself when evaluated.

Here is the code:

(require srfi/41)

(define (merge s1 s2)
  (stream-match s1 ((x . xs)
    (stream-match s2 ((y . ys)
      (if (< x y)
        (stream-cons x (merge xs s2))
        (stream-cons y (merge ys s1))))))))

(define (the-stream)
  (letrec ((s
    (stream-cons 1 (merge (stream-map     (lambda (x) (* 3 x)) s)
                          (stream-iterate (lambda (x) (* 2 x)) 2)))))
  s))

It's quite simple and fast compared to my other proposal, because it uses arithmetic properties of the problem besides monotonicity. I'm wrong, it can be generalized just as well (upcoming)

$ mzscheme -f feedback.scm -e '(display (stream->list (stream-take 20 (the-stream))))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f feedback.scm -e '(display (stream-ref (the-stream) 10000))'
161968247347450370721577384417107686788864605658546176
real    0m1.746s
user    0m1.344s
sys     0m0.156s

Using generators and a queue

We can also implement this with python's generators, but we need to use a queue to store the numbers waiting in the feedback loop:

# Merge the output of two generators
def merge(g1, g2):
    v1 = g1.next()
    v2 = g2.next()
    while 1:
        if v1 < v2:
            yield v1
            v1 = g1.next()
        else:
            yield v2
            v2 = g2.next()

# Generates the powers of 2, starting with n
def pow2(n):
    while 1: yield n; n *= 2

# Generates values shifted from the given 'q' and multiplied by 3
def mul3(q):
    while 1: yield q.pop(0) * 3

# The generator we want
def pow23():
    q = []
    v = 1
    g = merge(pow2(2), mul3(q))
    while 1:
        yield v
        q.append(v)
        v = g.next()

g23 = pow23()
for i in range(10000): g23.next()
print g23.next()

This is somewhat less elegant (IMHO), but the generators are much more lightweight:

$ time python feedback.py 
161968247347450370721577384417107686788864605658546176
real    0m0.150s
user    0m0.112s
sys     0m0.012s

For what is worth, I have done a scheme implementation (using closures as generators) which shows roughly the same performance.