Enumerating all 3-tuples

[Denis Kasak]

On 2018-03-10 02:13, Steven D'Aprano wrote:
> 
> 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.

If you want this exact order, it can be reproduced in the following way.

The triples can be viewed as a pair of a pair and a natural number:

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

Decomposing this by the diagonals yields

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

Notice that the first elements of each pair (i.e. the inner pairs) are 
given by the (inverse of the) original Cantor pairing function, in 
decreasing order. The second elements are just the natural numbers. 
Naming the inverse c, we can rewrite the above like this:

1: c(1),1
2: c(2),1  c(1),2
3: c(3),1  c(2),2  c(1),3
.
.
.

Rewriting this to spell out the mapping between the natural numbers and 
the pairs, we get

1 -> c(1),1
2 -> c(2),1
3 -> c(1),2
4 -> c(3),1
5 -> c(2),2
6 -> c(1),3
.
.
.

Squinting a bit, this might seem familiar. This is exactly the same as 
the original pairing function, except for an additional application of c 
to the first element of the pair!

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

This leads fairly naturally to the implementation.

     from itertools import accumulate, count

     def c(i):
         """
         Inverse of the Cantor pairing function, mapping N → N×N.
         """
         assert i >= 1

         # partial sums of the series 1 + 2 + 3 + ...
         sums = accumulate(count(1))
         n = 0

         while True:
             m = next(sums)
             if m < i:
                 n += 1
             else:
                 r = m - i
                 break

         return r + 1, n - r + 1


     def c3(i):
         """
         Inverse of the Cantor pairing function generalization to 
triples,
         mapping N → N×N×N.
         """
         n, m = c(i)
         return c(n) + (m,)

Applying c3 to the natural numbers gives the sequence you wanted:

>>> s = map(c3, count(1))
>>> pprint([next(s) for _ in range(10)])
[(1, 1, 1),
  (2, 1, 1),
  (1, 1, 2),
  (1, 2, 1),
  (2, 1, 2),
  (1, 1, 3),
  (3, 1, 1),
  (1, 2, 2),
  (2, 1, 3),
  (1, 1, 4)]

-- 
Denis Kasak