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