Rational number generator (Python)

Question

1. Why is it getting rid of the [1,3],[3,2] entry and replacing it with [2,3],[3,1]?

2. Note, [2,3],[3,1] is the correct branch, but it should not override the previous entry, it should be appended to it.

   def rational():
       treecount = 0
       tree = [[[1,1]]]
       left=[0,0]
       right=[0,0]
       while(True):
           treecount+=1
           tree.append([])
           left=[0,0]
           right=[0,0]
           for z in range(len(tree[treecount-1])):
               left[0] = tree[treecount-1][z][0]
               right[0] = tree[treecount-1][z][0] + tree[treecount-1][z][1]
               left[1] = tree[treecount-1][z][1] + tree[treecount-1][z][0]
               right[1] = tree[treecount-1][z][1]
               tree[treecount].append(left)
               tree[treecount].append(right)
               yield( tree)
   

Output looks like this:

[[[1, 1]], [[1, 2], [2, 1]]] [[[1, 1]], [[1, 2], [2, 1]], [[1, 3], [3, 2]]] [[[1, 1]], [[1, 2], [2, 1]], [[2, 3], [3, 1], [2, 3], [3, 1]]]

Answer 1

If you don't actually need the tree, but simply want to iterate over positive rationals, you can use this generator. Output is in the same order as a breadth-first traversal of the Calkin-Wilf tree, but without the cost of an ever-growing queue.

from fractions import Fraction
def Calkin_Wilf():
   x = Fraction(1, 1)
   yield x
   while True:
      x = Fraction(1, 2*Fraction(int(x))-x+1)
      yield x

Use the generator to create an iterator, then iterate with next(), e.g.:

rational = Calkin_Wilf()
for _ in range(100):
   print(next(rational))

Answer 2

You're running into a fundamental aspect of Python's object model, namely that Python never makes copies of objects implicitly.

In your code, you create two new lists left and right just before entering the for loop. You then repeatedly modify those two lists and append them to your tree so far. That's fine, except that all you're doing is appending references to the same two lists repeatedly.

Here's a simpler example of this phenomenon. We'll create a list left and append it to another list outer:

>>> outer = []
>>> left = [1, 3]
>>> outer.append(left)
>>> outer
[[1, 3]]

So far so good: everything's behaving as expected. But now let's modify left and append it to outer again:

>>> left[0] = 4
>>> outer.append(left)
>>> outer
[[4, 3], [4, 3]]

Notice how the first entry of outer has changed? That's because outer doesn't contain two independent lists at this point: instead, it contains two references to the same list. And that's what's happening in your code above.

It's straightforward to fix: create left and right afresh on every iteration of the for loop:

for z in range(len(tree[treecount-1])):
    left=[0, 0]
    right=[0, 0]
    left[0] = tree[treecount-1][z][0]
    right[0] = tree[treecount-1][z][0] + tree[treecount-1][z][1]
    left[1] = tree[treecount-1][z][1] + tree[treecount-1][z][0]
    <and so on>

Alternatively, you can make copies of left and right before appending them:

tree[treecount].append(list(left))
tree[treecount].append(list(right))

Incidentally, you can simplify your code substantially if you make better use of some of Python's idioms. First, iterating over range(len(something)) is often unnecessary, especially when you're going to use the values directly as indices. Iterate directly over the list instead. Second, you can unpack the tree[treecount-1] value directly in the for statement. Then you can use negative indices to index from the end of the list, saving you the need to maintain treecount. With those first-pass changes, your code looks like this:

def rational():
    tree = [[[1,1]]]
    while True:
        tree.append([])
        for a, b in tree[-2]:
            left = [a, b + a]
            right = [a + b, b]
            tree[-1].extend([left, right])
            yield tree

There's still room for improvement, but this is already much more readable than the original code.