I am trying to enumerate all the three-tuples (x, y, z) where each of x,
y, z can range from 1 to ∞ (infinity).
This is clearly unhelpful:
for x in itertools.count(1):
for y in itertools.count(1):
for z in itertools.count(1):
print(x, y, z)
as it never advances beyond x=1, y=1 since the innermost loop never
finishes.
Georg Cantor to the rescue! (Well, almost...)
https://en.wikipedia.org/wiki/Pairing_function
The Russian mathematician Cantor came up with a *pairing function* that
encodes a pair of integers into a single one. For example, he maps the
coordinate pairs to integers as follows:
1,1 -> 1
2,1 -> 2
1,2 -> 3
3,1 -> 4
2,2 -> 5
and so forth. He does this by writing out the coordinates in a grid:
1,1 1,2 1,3 1,4 ...
2,1 2,2 2,3 2,4 ...
3,1 3,2 3,3 3,4 ...
4,1 4,2 4,3 4,4 ...
...
and then iterating over them along the diagonals, starting from the top
corner. That's just what I'm after, and I have this function that works
for 2-tuples:
def cantor(start=0):
"""Yield coordinate pairs using Cantor's Pairing Function.
Yields coordinate pairs in (Z*,Z*) over the diagonals:
>>> it = cantor()
>>> [next(it) for _ in range(10)]
[(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3)]
If ``start`` is given, it is used as the first x- and y-coordinate.
"""
i = start
while True:
for j in range(start, i+1):
yield (i-j+start, j)
i += 1
But I've stared at this for an hour and I can't see how to extend the
result to three coordinates. I can lay out a grid in the order I want:
1,1,1 1,1,2 1,1,3 1,1,4 ...
2,1,1 2,1,2 2,1,3 2,1,4 ...
1,2,1 1,2,2 1,2,3 1,2,4 ...
3,1,1 3,1,2 3,1,3 3,1,4 ...
2,2,1 2,2,2 2,2,3 2,2,4 ...
...
and applying Cantor's diagonal order will give me what I want, but damned
if I can see how to do it in code.
Clearly I'm having a "cannot brain today" moment.
Can anyone help me out here?
