Enumerating all 3-tuples

[MRAB]

On 2018-03-10 01:13, Steven D'Aprano wrote:
> 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?
> 
Think about the totals of each triple. You'll get totals of 3, then 
totals of 4, etc.

This might help, although the order they come out might not be what you 
want:

def triples():
     for total in itertools.count(1):
         for i in range(1, total):
             for j in range(1, total - i):
                 yield i, j, total - (i + j)