Enumerating all 3-tuples

[Ben Bacarisse]

Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:

> 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.

Rather than a grid you would need a cube, and the diagonals become
planes.  But I think that is an easier way (no code yet though!) unless
you are set on one particular enumeration: consider the triple as a pair
one element of which runs over the enumeration of pairs you already
have.

Start with

  1,1  <->  1
  2,1  <->  2
  1,2  <->  3
  3,1  <->  4
  2,2  <->  5
  1,3  <->  6
  ...

but replace the first element by the numbered pair from this same list:

  (1,1),1
  (2,1),1
  (1,1),2
  (1,2),1
  (2,1),2
  (1,1),3
  ...

If it were a sane time here I'd try to code this.  Looks like fun but it
must wait...

-- 
Ben.