Enumerating all 3-tuples

[Denis Kasak]

On 2018-03-13 23:56, Denis Kasak wrote:
> 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.
> 
[snip]
> 
> 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 ...
>    .       .       .
>    .       .       .
>    .       .       .
[snip]
>     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,)

In fact, extending this idea further, we can view the grid as a 
Cartesian product of two sets: the natural numbers and an arbitrary 
enumerable set. In your intended grid layout, the natural numbers were 
put (in their usual ordering) on the horizontal axis and the 2-tuples 
given by the pairing function on the vertical axis.

However, diagonalizing this grid allows us to enumerate the Cartesian 
product itself, which means we can repeat the process by using this 
enumeration as the new vertical axis. Therefore, this process 
generalizes naturally to an arbitrary number of dimensions:

     def cr(i, d=2):
         """
         Inverse of the Cantor pairing function generalization to 
d-tuples,
         mapping N → N^d.
         """
         if d == 1:
             return i
         elif d == 2:
             return c(i)
         else:
             n, m = c(i)
             return cr(n, d-1) + (m,)


     >>> def first_ten(d):
     ...    return [cr(i, d) for i in range(1, 11)]

     >>> for d in range(2, 5):
     ...     pprint(first_ten(d))
     [(1, 1), (2, 1), (1, 2), (3, 1), (2, 2), (1, 3), (4, 1), (3, 2), (2, 
3), (1, 4)]
     [(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)]
     [(1, 1, 1, 1),
     (2, 1, 1, 1),
     (1, 1, 1, 2),
     (1, 1, 2, 1),
     (2, 1, 1, 2),
     (1, 1, 1, 3),
     (1, 2, 1, 1),
     (1, 1, 2, 2),
     (2, 1, 1, 3),
     (1, 1, 1, 4)]


-- 
Denis Kasak