Enumerating all 3-tuples

Denis Kasak dkasak at termina.org.uk
Thu Mar 15 09:09:16 EDT 2018


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



More information about the Python-list mailing list