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
--
https://mail.python.org/mailman/listinfo/python-list
