Re: Enumerating all 3-tuples

[Robin Becker]

On 21/03/2018 05:14, Steven D'Aprano wrote:

On Tue, 13 Mar 2018 23:56:37 +0100, Denis Kasak wrote:

[...]

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 ...


[...]

This leads fairly naturally to the implementation.

  from itertools import accumulate, count

  def c(i):
  """

...

That looks interesting, I haven't had a chance to play with it in a lot
of detail yet, but it looks to me like every time you generate a triple,
it starts counting up from 1.

So iterating over c3(1), c3(2), c3(4), ... c3(something big) is going to
have O(N**2) performance. It's like the old joke about the Polish painter:


This cantor inverse is much faster; it uses the integer sqrt from here

http://code.activestate.com/recipes/577821-integer-square-root-function/

so far as I can tell it works for the cantor below

def cantor(k1,k2):
return (((k1+k2)*(k1+k2+1))>>1) + k2

def isqrt(x):
if x < 0:
raise ValueError('square root not defined for negative numbers')
n = int(x)
if n == 0:
return 0
a, b = divmod(n.bit_length(), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y

def inverse_cantor(z):
w = int((isqrt(8*z+1)-1)//2)
t = (w*(w+1))>>1
j = z - t
i = w - j
return i, j

but it doesn't agree with Denis' inverse I guess because this is defined on non-negative integers, but his functions are defined 
on positive integers.



http://global.joelonsoftware.com/English/Articles/BacktoBasics.html

Since that's exactly what I need to do, that might be a problem.

On the other hand, I doubt I'll need to generate more than a few thousand
of these, so it might be fast enough. I guess I have to run some
benchmarks to find out.

But however they turn out, I appreciate your time and code. Thanks heaps!






--
Robin Becker

--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Steven D'Aprano]

On Tue, 13 Mar 2018 23:56:37 +0100, Denis Kasak wrote:

[...]
> 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 ...

[...]
> 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:


Thanks!

That looks interesting, I haven't had a chance to play with it in a lot 
of detail yet, but it looks to me like every time you generate a triple, 
it starts counting up from 1.

So iterating over c3(1), c3(2), c3(4), ... c3(something big) is going to 
have O(N**2) performance. It's like the old joke about the Polish painter:

http://global.joelonsoftware.com/English/Articles/BacktoBasics.html

Since that's exactly what I need to do, that might be a problem.

On the other hand, I doubt I'll need to generate more than a few thousand 
of these, so it might be fast enough. I guess I have to run some 
benchmarks to find out.

But however they turn out, I appreciate your time and code. Thanks heaps!



-- 
Steve

-- 
https://mail.python.org/mailman/listinfo/python-list

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

Re: Enumerating all 3-tuples (Posting On Python-List Prohibited)

[Ben Bacarisse]

Lawrence D’Oliveiro  writes:

> On Thursday, March 15, 2018 at 2:56:24 PM UTC+13, Ben Bacarisse wrote:
>>
>> Lawrence D’Oliveiro writes:
>> 
>>> On Wednesday, March 14, 2018 at 2:18:24 PM UTC+13, Ben Bacarisse wrote:
>>>
 Lawrence D’Oliveiro writes:
 
 The original problem -- triples of natural numbers -- is
 not particularly hard, but the general problem -- enumerating n-tuples
 of some sequence -- is more interesting because it is a bit harder.
>>>
>>> It’s not harder--it’s exactly the same difficulty. You iterate the
>>> naturals, then interpose a function mapping them onto the set that you
>>> really want to use.
>> 
>> Yes, I said exactly that a couple of messages ago.
>
> I see. So you said it is a bit harder, and you also said it’s not
> harder at all. Got it.

Yes, I was not clear.  It was the point about mapping from a solution
that uses the natural numbers that's I mentioned before.  The "bit
harder" comes from generalising to n-tuples.

(I get the feeling I should apologise for something because I think I
have annoyed or irritated you.  I'm sure I don't always get the right
tone but I really hope I've not been rude.  I'm sorry if I have been.)

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples (Posting On Python-List Prohibited)

[Ben Bacarisse]

Lawrence D’Oliveiro  writes:

> On Wednesday, March 14, 2018 at 2:18:24 PM UTC+13, Ben Bacarisse wrote:
>> Lawrence D’Oliveiro writes:
>> 
>> The original problem -- triples of natural numbers -- is
>> not particularly hard, but the general problem -- enumerating n-tuples
>> of some sequence -- is more interesting because it is a bit harder.
>
> It’s not harder--it’s exactly the same difficulty. You iterate the
> naturals, then interpose a function mapping them onto the set that you
> really want to use.

Yes, I said exactly that a couple of messages ago.

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

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

Re: Enumerating all 3-tuples (Posting On Python-List Prohibited)

[Ben Bacarisse]

Lawrence D’Oliveiro  writes:

> On Tuesday, March 13, 2018 at 1:58:48 PM UTC+13, Ben Bacarisse wrote:
>> Of course you can always generate n-tuples of N and then map these to
>> n-tuples of the intended sequence but that seems inelegant.
>
> This whole discussion seems to be going off on esoteric, irrelevant
> tangents. The problem was not that hard to solve.

Sure, but that's one thing that makes Usenet (and email lists)
interesting.  The original problem -- triples of natural numbers -- is
not particularly hard, but the general problem -- enumerating n-tuples
of some sequence -- is more interesting because it is a bit harder.

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Robin Becker]

On 13/03/2018 11:14, Steven D'Aprano wrote:

On Mon, 12 Mar 2018 13:17:15 +, Robin Becker wrote:


It's possible to generalize the cantor pairing function to triples, but
that may not give you what you want. Effectively you can generate an
arbitrary number of triples using an iterative method. My sample code
looked like this


import math

def cantor_pair(k1,k2):
return (((k1+k2)*(k1+k2+1))>>1) + k2

def inverse_cantor_pair(z):
w = int((math.sqrt(8*z+1)-1)/2.0)
t = (w*(w+1))>>1
j = z - t
i = w - j
return i, j


I definitely want to avoid any round trips through float in order to use
sqrt.


But thanks for the code, I'll certainly steal it, er I mean study it for
future reference :-)



well I guess Cantor didn't worry about rounding errors :)

For high z there's an integer square root function which seems to work pretty 
well here
http://code.activestate.com/recipes/577821-integer-square-root-function/

I'm not sure if there are any other sensible invertible pairing functions on non-negative integers; this page mentions a couple 
implemented in matlab


https://uk.mathworks.com/matlabcentral/fileexchange/44253-three-different-bijections-or-pairing-functions-between-n-and-n%5E2--including-cantor-polynomials-

and this describes the elegant pairing more

http://szudzik.com/ElegantPairing.pdf

It seems reasonable that a mapping N x N --> N should require a square root in 
the inverse.
--
Robin Becker

--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Antoon Pardon]

On 10-03-18 02:13, Steven D'Aprano wrote:
> I am trying to enumerate all the three-tuples (x, y, z) where each of x, 
> y, z can range from 1 to ∞ (infinity).
>
> This is clearly unhelpful:
>
> for x in itertools.count(1):
> for y in itertools.count(1):
> for z in itertools.count(1):
> print(x, y, z)
>
> as it never advances beyond x=1, y=1 since the innermost loop never 
> finishes.
>
> Georg Cantor to the rescue! (Well, almost...)
>
> https://en.wikipedia.org/wiki/Pairing_function

I came up with the following generalisation:

from itertools import count

def summation2(total):
for n in range(1, total):
yield n, total - n

def summation(total, n):
if n == 2:
yield from summation2(total)
else:
for i in range(1, total - n + 2):
for tail in summation(total - i, n - 1):
yield (i,) + tail


def cantor(n):
for total in count(n):
yield from summation(total, n)

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Paul Moore]

On 13 March 2018 at 11:01, Steven D'Aprano
 wrote:
> On Sat, 10 Mar 2018 11:15:49 +, Paul Moore wrote:
>
>> On 10 March 2018 at 02:18, MRAB  wrote:
> [...]
>>> This might help, although the order they come out might not be what you
>>> want:
>>>
>>> def triples():
>>> for total in itertools.count(1):
>>> for i in range(1, total):
>>> for j in range(1, total - i):
>>> yield i, j, total - (i + j)
>>
>> Mathematically, that's the usual generalisation of Cantor's diagonal
>> argument.
>
> Thanks MRAB. Paul, do you have a reference for that? Wolfram Mathworld is
> not very helpful regarding generalising Cantor's diagonalisation pairing
> function.
>
> (It's not the diagonal argument, that's something else :-)

Sadly, other than my memories of my maths degree from 30 years ago, no
I don't. I'll see if I can dig something out.

Paul
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Steven D'Aprano]

On Mon, 12 Mar 2018 13:17:15 +, Robin Becker wrote:

> It's possible to generalize the cantor pairing function to triples, but
> that may not give you what you want. Effectively you can generate an
> arbitrary number of triples using an iterative method. My sample code
> looked like this
> 
> 
> import math
> 
> def cantor_pair(k1,k2):
>   return (((k1+k2)*(k1+k2+1))>>1) + k2
> 
> def inverse_cantor_pair(z):
>   w = int((math.sqrt(8*z+1)-1)/2.0)
>   t = (w*(w+1))>>1
>   j = z - t
>   i = w - j
>   return i, j

I definitely want to avoid any round trips through float in order to use 
sqrt.


But thanks for the code, I'll certainly steal it, er I mean study it for 
future reference :-)


-- 
Steve

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples (Posting On Python-List Prohibited)

[Steven D'Aprano]

On Sun, 11 Mar 2018 01:40:01 +, Ben Bacarisse wrote:

> I'm sure deep recursion is not needed, it's just tricky translating from
> a lazy language when one is not familiar with all the iterator
> facilities in Python.  For example, I couldn't find an append operation
> that returns an iterable.

The Python iterator protocol is intentionally lightweight, so there's no 
"append" operation and + is not supported.

But you can call

it = itertools.chain(it, iterator2)



It's not often that I think Ruby's ability to monkey-patch arbitrary 
objects including built-ins is a good idea, but the ability to allow 
iterator+iterator is *almost* one of those times.


-- 
Steve

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Steven D'Aprano]

On Sat, 10 Mar 2018 11:15:49 +, Paul Moore wrote:

> On 10 March 2018 at 02:18, MRAB  wrote:
[...]
>> This might help, although the order they come out might not be what you
>> want:
>>
>> def triples():
>> for total in itertools.count(1):
>> for i in range(1, total):
>> for j in range(1, total - i):
>> yield i, j, total - (i + j)
> 
> Mathematically, that's the usual generalisation of Cantor's diagonal
> argument.

Thanks MRAB. Paul, do you have a reference for that? Wolfram Mathworld is 
not very helpful regarding generalising Cantor's diagonalisation pairing 
function.

(It's not the diagonal argument, that's something else :-)


-- 
Steve

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Robin Becker]

On 12/03/2018 18:05, Chris Angelico wrote:

On Tue, Mar 13, 2018 at 2:54 AM, Robin Becker  wrote:

On 12/03/2018 13:17, Robin Becker wrote:
An alternative approach gives more orderly sequences using a variable base
number construction


4 (0, 0, 1)
9 (0, 0, 1)
18 (0, 0, 2)
32 (0, 0, 2)


I spy duplicates.

ChrisA


oh well there goes that idea :(

--
Robin Becker

--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples (Posting On Python-List Prohibited)

[Ben Bacarisse]

Lawrence D’Oliveiro  writes:

> On Sunday, March 11, 2018 at 2:40:16 PM UTC+13, Ben Bacarisse wrote:
>> It would be nice to avoid relying on any value-based ordering.
>
> I don’t see why. The set of elements has to have the same cardinality
> as the set of natural numbers, after all. Why not take advantage of
> that?

Maybe we are saying the same thing?  The elements from which the tuple
members are drawn need only be a sequence defined by a successor
function.  The values themselves need have no ordering nor, indeed, have
any of the arithmetic properties of N.

Of course you can always generate n-tuples of N and then map these to
n-tuples of the intended sequence but that seems inelegant.

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Chris Angelico]

On Tue, Mar 13, 2018 at 5:42 AM, Skip Montanaro
 wrote:
 4 (0, 0, 1)
 9 (0, 0, 1)
 18 (0, 0, 2)
 32 (0, 0, 2)
>>
>> I spy duplicates.
>
> I didn't realize we'd started playing "I Spy."
> 

We're actually playing Calvinball, but don't tell the others.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Skip Montanaro]

>>> 4 (0, 0, 1)
>>> 9 (0, 0, 1)
>>> 18 (0, 0, 2)
>>> 32 (0, 0, 2)
>
> I spy duplicates.

I didn't realize we'd started playing "I Spy

."
​ ​

Skip
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Chris Angelico]

On Tue, Mar 13, 2018 at 2:54 AM, Robin Becker  wrote:
> On 12/03/2018 13:17, Robin Becker wrote:
> An alternative approach gives more orderly sequences using a variable base
> number construction
>
>> 4 (0, 0, 1)
>> 9 (0, 0, 1)
>> 18 (0, 0, 2)
>> 32 (0, 0, 2)

I spy duplicates.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Robin Becker]

On 12/03/2018 13:17, Robin Becker wrote:
It's possible to generalize the cantor pairing function to triples, but that may not give you what you want. Effectively you can 
generate an arbitrary number of triples using an iterative method. My sample code looked like this

ct mapping of non-negative integers to triplets.

An alternative approach gives more orderly sequences using a variable base 
number construction

class Tupilator(object):
def __init__(self,degree=3):
self.i = 0
self.n = 2
self.degree = degree

def next(self):
x = self.i
v = []
a =v.append
n = self.n
if not x: a(0)
while x>0:
x, d = divmod(x,n)
a(d)
if sum(v)==self.degree*(n-1):
self.n += 1
pad = self.degree - len(v)
if pad>0:
v += pad*[0]
self.i += 1
return tuple(v)

if __name__=='__main__':
t = Tupilator()
for z in xrange(100):
print z, t.next()


0 (0, 0, 0)
1 (1, 0, 0)
2 (0, 1, 0)
3 (1, 1, 0)
4 (0, 0, 1)
5 (1, 0, 1)
6 (0, 1, 1)
7 (1, 1, 1)
8 (2, 2, 0)
9 (0, 0, 1)
10 (1, 0, 1)
11 (2, 0, 1)
12 (0, 1, 1)
13 (1, 1, 1)
14 (2, 1, 1)
15 (0, 2, 1)
16 (1, 2, 1)
17 (2, 2, 1)
18 (0, 0, 2)
19 (1, 0, 2)
20 (2, 0, 2)
21 (0, 1, 2)
22 (1, 1, 2)
23 (2, 1, 2)
24 (0, 2, 2)
25 (1, 2, 2)
26 (2, 2, 2)
27 (3, 2, 1)
28 (0, 3, 1)
29 (1, 3, 1)
30 (2, 3, 1)
31 (3, 3, 1)
32 (0, 0, 2)
33 (1, 0, 2)
34 (2, 0, 2)
35 (3, 0, 2)
36 (0, 1, 2)
37 (1, 1, 2)
38 (2, 1, 2)
39 (3, 1, 2)
40 (0, 2, 2)



80 (0, 1, 3)
81 (1, 1, 3)
82 (2, 1, 3)
83 (3, 1, 3)
84 (4, 1, 3)
85 (0, 2, 3)
86 (1, 2, 3)
87 (2, 2, 3)
88 (3, 2, 3)
89 (4, 2, 3)
90 (0, 3, 3)
91 (1, 3, 3)
92 (2, 3, 3)
93 (3, 3, 3)
94 (4, 3, 3)
95 (0, 4, 3)
96 (1, 4, 3)
97 (2, 4, 3)
98 (3, 4, 3)
99 (4, 4, 3)





--
Robin Becker

--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Elliott Roper]

On 10 Mar 2018, Paul Moore wrote
(in article):

> On 10 March 2018 at 02:18, MRAB  wrote:
> > On 2018-03-10 01:13, Steven D'Aprano wrote:
> > >
> > > I am trying to enumerate all the three-tuples (x, y, z) where each of x,
> > > y, z can range from 1 to ∞ (infinity).
> > >
> > > This is clearly unhelpful:
> > >
> > > for x in itertools.count(1):
> > > for y in itertools.count(1):
> > > for z in itertools.count(1):
> > > print(x, y, z)
> > >
> > > as it never advances beyond x=1, y=1 since the innermost loop never
> > > finishes.
> > >
> > > Georg Cantor to the rescue! (Well, almost...)
> [...]
> > > Can anyone help me out here?
> > Think about the totals of each triple. You'll get totals of 3, then totals
> > of 4, etc.
> >
> > This might help, although the order they come out might not be what you
> > want:
> >
> > def triples():
> > for total in itertools.count(1):
> > for i in range(1, total):
> > for j in range(1, total - i):
> > yield i, j, total - (i + j)
>
> Mathematically, that's the usual generalisation of Cantor's diagonal argument.
>
> Paul

Would a multi-dimensional Hilbert curve do the job? See the Wikipedia article 
for starters

-- 
To de-mung my e-mail address:- fsnospam$elliott$$ PGP Fingerprint: 1A96 3CF7 
637F 896B C810 E199 7E5C A9E4 8E59 E248

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Robin Becker]

It's possible to generalize the cantor pairing function to triples, but that may not give you what you want. Effectively you can 
generate an arbitrary number of triples using an iterative method. My sample code looked like this



import math

def cantor_pair(k1,k2):
return (((k1+k2)*(k1+k2+1))>>1) + k2

def inverse_cantor_pair(z):
w = int((math.sqrt(8*z+1)-1)/2.0)
t = (w*(w+1))>>1
j = z - t
i = w - j
return i, j

def cantor_triple(i,j,k):
return cantor_pair(cantor_pair(i,j),k)

def inverse_cantor_triple(z):
j,k = inverse_cantor_pair(z)
i,j = inverse_cantor_pair(j)
return i,j,k

if __name__=='__main__':
for z in xrange(100):
i,j,k = inverse_cantor_triple(z)
print z, repr((i,j,k))


or changing the construction

import math

def cantor_pair(k1,k2):
return (((k1+k2)*(k1+k2+1))>>1) + k2

def inverse_cantor_pair(z):
w = int((math.sqrt(8*z+1)-1)/2.0)
t = (w*(w+1))>>1
j = z - t
i = w - j
return i, j

def cantor_triple(i,j,k):
return cantor_pair(i,cantor_pair(j,k))

def inverse_cantor_triple(z):
i,k = inverse_cantor_pair(z)
j,k = inverse_cantor_pair(k)
return i,j,k

if __name__=='__main__':
for z in xrange(100):
i,j,k = inverse_cantor_triple(z)
print z, repr((i,j,k)), cantor_triple(i,j,k)==z

this give different outcomes, but both appear to be a correct mapping of 
non-negative integers to triplets.
--
Robin Becker

--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples (Posting On Python-List Prohibited)

[Ben Bacarisse]

Lawrence D’Oliveiro  writes:

> On Sunday, March 11, 2018 at 3:24:05 AM UTC+13, Ben Bacarisse wrote:
>> Unfortunately my Python is not up to using iterators well enough to
>> avoid a "maximum recursion depth exceeded" error.
>
> My solution only needed recursion up to a depth equal to the length of
> the tuples. The ordering is done based on the maximum value of any
> element of the tuple.

I'm sure deep recursion is not needed, it's just tricky translating from
a lazy language when one is not familiar with all the iterator
facilities in Python.  For example, I couldn't find an append operation
that returns an iterable.

It would be nice to avoid relying on any value-based ordering.  There is
inevitably an order that comes from the iterable whose elements are
being paired, trippled or whatever, but that's all that's really
required for a solution.

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Ben Bacarisse]

bartc  writes:

> On 10/03/2018 20:06, Ben Bacarisse wrote:
>>> On 10/03/2018 14:23, Ben Bacarisse wrote:

 Off topic: I knocked up this Haskell version as a proof-of-concept:

 import Data.List

 pn n l = pn' n (map (:[]) l)
  where pn' n lists | n == 1 = lists
| otherwise = diag (pn' (n-1) lists) lists
diag l1 l2 = zipWith (++) (concat (inits l1))
  (concat (map reverse (inits 
 l2)))


>> but, as I've said, the order of the results is not the usual one (except
>> for pairs).

> OK. I ran it like this:
>
>  main = print (take 20 (pn 3 [1..]))
>
> But I'm trying to understand the patterns in the sequence. If I use:
>
>  main = print (take 50 (pn 2 [1..]))
>
> then group the results into sets of 1, 2, 3, etc pairs, showing each
> group on a new line, then this gives sequences which are equivalent to
> the diagonals of the OP's 2D grid. (Except they don't alternate in
> direction; is that what you mean?)

Yes, the pattern for pairs (pn 2 [1..]) is the normal one (one of them
anyway).  In the 2D grid the diagonals are lines of equal sum (for a
numeric grid, of course) and all the pairs that sum to x appear before
those that sum to x+1:

*Main> take 28 $ map sum $ pn 2 [1..]
[2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8,8,8,8]

The recursive step breaks this rule.  I'm sure there's a better rule,
but it's getting more and more off-topic...

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[bartc]

On 10/03/2018 20:06, Ben Bacarisse wrote:

bartc  writes:


[repost as original seems to have gone to email; my newsreader has
somehow acquired a 'Reply' button where 'Followup' normally goes.]


[I thought it was intended but my reply bounced.]


On 10/03/2018 14:23, Ben Bacarisse wrote:

Ben Bacarisse  writes:



Off topic: I knocked up this Haskell version as a proof-of-concept:

import Data.List

pn n l = pn' n (map (:[]) l)
 where pn' n lists | n == 1 = lists
   | otherwise = diag (pn' (n-1) lists) lists
   diag l1 l2 = zipWith (++) (concat (inits l1))
 (concat (map reverse (inits l2)))




What's the output? (And what's the input; how do you invoke pn, if
that's how it's done?)


You pass a number and a list which should probably be infinite like
[1..].  You'd better take only a few of the resulting elements then:

*Main> let triples = pn 3 [1..]
*Main> take 20 triples
[[1,1,1],[1,1,2],[1,2,1],[1,1,3],[1,2,2],[2,1,1],[1,1,4],[1,2,3],[2,1,2],[1,3,1],[1,1,5],[1,2,4],[2,1,3],[1,3,2],[2,2,1],[1,1,6],[1,2,5],[2,1,4],[1,3,3],[2,2,2]]

or you can index the list to look at particular elements:

*Main> triples !! 1000
[70,6,1628]

but, as I've said, the order of the results is not the usual one (except
for pairs).


OK. I ran it like this:

 main = print (take 20 (pn 3 [1..]))

But I'm trying to understand the patterns in the sequence. If I use:

 main = print (take 50 (pn 2 [1..]))

then group the results into sets of 1, 2, 3, etc pairs, showing each 
group on a new line, then this gives sequences which are equivalent to 
the diagonals of the OP's 2D grid. (Except they don't alternate in 
direction; is that what you mean?)


I'll have to study the pn 3 version some more. (pn 10 gives an 
interesting view of it too.)


--
bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Ben Bacarisse]

bartc  writes:

> [repost as original seems to have gone to email; my newsreader has
> somehow acquired a 'Reply' button where 'Followup' normally goes.]

[I thought it was intended but my reply bounced.]

> On 10/03/2018 14:23, Ben Bacarisse wrote:
>> Ben Bacarisse  writes:
>
>> Off topic: I knocked up this Haskell version as a proof-of-concept:
>>
>>import Data.List
>>
>>pn n l = pn' n (map (:[]) l)
>> where pn' n lists | n == 1 = lists
>>   | otherwise = diag (pn' (n-1) lists) lists
>>   diag l1 l2 = zipWith (++) (concat (inits l1))
>> (concat (map reverse (inits l2)))
>>

> What's the output? (And what's the input; how do you invoke pn, if
> that's how it's done?)

You pass a number and a list which should probably be infinite like
[1..].  You'd better take only a few of the resulting elements then:

*Main> let triples = pn 3 [1..]
*Main> take 20 triples
[[1,1,1],[1,1,2],[1,2,1],[1,1,3],[1,2,2],[2,1,1],[1,1,4],[1,2,3],[2,1,2],[1,3,1],[1,1,5],[1,2,4],[2,1,3],[1,3,2],[2,2,1],[1,1,6],[1,2,5],[2,1,4],[1,3,3],[2,2,2]]

or you can index the list to look at particular elements:

*Main> triples !! 1000
[70,6,1628]

but, as I've said, the order of the results is not the usual one (except
for pairs).

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[bartc]

[repost as original seems to have gone to email; my newsreader has 
somehow acquired a 'Reply' button where 'Followup' normally goes.]


On 10/03/2018 14:23, Ben Bacarisse wrote:

Ben Bacarisse  writes:



Off topic: I knocked up this Haskell version as a proof-of-concept:

   import Data.List

   pn n l = pn' n (map (:[]) l)
where pn' n lists | n == 1 = lists
  | otherwise = diag (pn' (n-1) lists) lists
  diag l1 l2 = zipWith (++) (concat (inits l1))
(concat (map reverse (inits l2)))

Notes:

map (:[]) l turns [1, 2, 3, ...] into [[1], [2], [3], ...]

inits gives the list of initial segments of l.  I.e. (inits "abc") is
["", "a", "ab", "abc"].

concat joins a list of lists into one list.

zipWith (++) l1 l2 makes a list by pair-wise appending the elements of
l1 and l2.



What's the output? (And what's the input; how do you invoke pn, if 
that's how it's done?)



--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Ben Bacarisse]

Sorry for following up to myself again...

Ben Bacarisse  writes:

>> ...  But I think that is an easier way (no code yet though!) unless
>> you are set on one particular enumeration: consider the triple as a pair
>> one element of which runs over the enumeration of pairs you already
>> have.


This algorithm has the disadvantage that the sequence is not any of the
usual "zig-zag" patterns.  Using numbers, for example the sums of the
triples are not monotonic:

*Main> take 30 $ map sum (pn 2 [1..])
[3,4,4,5,5,4,6,6,5,5,7,7,6,6,5,8,8,7,7,6,5,9,9,8,8,7,6,6,10,10]

That probably makes it a non-starter for you.

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Ben Bacarisse]

Ben Bacarisse  writes:

> Steven D'Aprano  writes:
>
>> I am trying to enumerate all the three-tuples (x, y, z) where each of x, 
>> y, z can range from 1 to ∞ (infinity).


> ...  But I think that is an easier way (no code yet though!) unless
> you are set on one particular enumeration: consider the triple as a pair
> one element of which runs over the enumeration of pairs you already
> have.
>
> Start with
>
>   1,1  <->  1
>   2,1  <->  2
>   1,2  <->  3
>   3,1  <->  4
>   2,2  <->  5
>   1,3  <->  6
>   ...
>
> but replace the first element by the numbered pair from this same list:
>
>   (1,1),1
>   (2,1),1
>   (1,1),2
>   (1,2),1
>   (2,1),2
>   (1,1),3
>   ...
>
> If it were a sane time here I'd try to code this.  Looks like fun but it
> must wait...

One advantage of this method is that is does rely on any numeric
properties of the base list.  Any sequence-like object can be used to
make an list of n-tuples.

Unfortunately my Python is not up to using iterators well enough to
avoid a "maximum recursion depth exceeded" error.  Basically everything
must be kept "lazy" and I'm not sure how to do that in Python.  It will
help my Python to learn so I will have a go.

Off topic: I knocked up this Haskell version as a proof-of-concept:

  import Data.List

  pn n l = pn' n (map (:[]) l)
   where pn' n lists | n == 1 = lists
 | otherwise = diag (pn' (n-1) lists) lists
 diag l1 l2 = zipWith (++) (concat (inits l1))
   (concat (map reverse (inits l2)))

Notes:

map (:[]) l turns [1, 2, 3, ...] into [[1], [2], [3], ...]

inits gives the list of initial segments of l.  I.e. (inits "abc") is
["", "a", "ab", "abc"].

concat joins a list of lists into one list.

zipWith (++) l1 l2 makes a list by pair-wise appending the elements of
l1 and l2.

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Paul Moore]

On 10 March 2018 at 02:18, MRAB  wrote:
> On 2018-03-10 01:13, Steven D'Aprano wrote:
>>
>> I am trying to enumerate all the three-tuples (x, y, z) where each of x,
>> y, z can range from 1 to ∞ (infinity).
>>
>> This is clearly unhelpful:
>>
>> for x in itertools.count(1):
>>  for y in itertools.count(1):
>>  for z in itertools.count(1):
>>  print(x, y, z)
>>
>> as it never advances beyond x=1, y=1 since the innermost loop never
>> finishes.
>>
>> Georg Cantor to the rescue! (Well, almost...)
[...]
>> Can anyone help me out here?
>>
> Think about the totals of each triple. You'll get totals of 3, then totals
> of 4, etc.
>
> This might help, although the order they come out might not be what you
> want:
>
> def triples():
> for total in itertools.count(1):
> for i in range(1, total):
> for j in range(1, total - i):
> yield i, j, total - (i + j)

Mathematically, that's the usual generalisation of Cantor's diagonal argument.

Paul
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Ben Bacarisse]

Steven D'Aprano  writes:

> I am trying to enumerate all the three-tuples (x, y, z) where each of x, 
> y, z can range from 1 to ∞ (infinity).
>
> This is clearly unhelpful:
>
> for x in itertools.count(1):
> for y in itertools.count(1):
> for z in itertools.count(1):
> print(x, y, z)
>
> as it never advances beyond x=1, y=1 since the innermost loop never 
> finishes.
>
> Georg Cantor to the rescue! (Well, almost...)
>
> https://en.wikipedia.org/wiki/Pairing_function
>
> The Russian mathematician Cantor came up with a *pairing function* that 
> encodes a pair of integers into a single one. For example, he maps the 
> coordinate pairs to integers as follows:
>
> 1,1  ->  1
> 2,1  ->  2
> 1,2  ->  3
> 3,1  ->  4
> 2,2  ->  5
>
> and so forth. He does this by writing out the coordinates in a grid:
>
> 1,1  1,2  1,3  1,4  ...
> 2,1  2,2  2,3  2,4  ...
> 3,1  3,2  3,3  3,4  ...
> 4,1  4,2  4,3  4,4  ...
> ...
>
> and then iterating over them along the diagonals, starting from the top 
> corner. That's just what I'm after, and I have this function that works 
> for 2-tuples:
>
> def cantor(start=0):
> """Yield coordinate pairs using Cantor's Pairing Function.
>
> Yields coordinate pairs in (Z*,Z*) over the diagonals:
>
> >>> it = cantor()
> >>> [next(it) for _ in range(10)]
> [(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3)]
>
> If ``start`` is given, it is used as the first x- and y-coordinate.
> """
> i = start
> while True:
> for j in range(start, i+1):
> yield (i-j+start, j)
> i += 1
>
>
> 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.

Rather than a grid you would need a cube, and the diagonals become
planes.  But I think that is an easier way (no code yet though!) unless
you are set on one particular enumeration: consider the triple as a pair
one element of which runs over the enumeration of pairs you already
have.

Start with

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

but replace the first element by the numbered pair from this same list:

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

If it were a sane time here I'd try to code this.  Looks like fun but it
must wait...

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[MRAB]

On 2018-03-10 01:13, Steven D'Aprano wrote:

I am trying to enumerate all the three-tuples (x, y, z) where each of x,
y, z can range from 1 to ∞ (infinity).

This is clearly unhelpful:

for x in itertools.count(1):
 for y in itertools.count(1):
 for z in itertools.count(1):
 print(x, y, z)

as it never advances beyond x=1, y=1 since the innermost loop never
finishes.

Georg Cantor to the rescue! (Well, almost...)

https://en.wikipedia.org/wiki/Pairing_function

The Russian mathematician Cantor came up with a *pairing function* that
encodes a pair of integers into a single one. For example, he maps the
coordinate pairs to integers as follows:

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

and so forth. He does this by writing out the coordinates in a grid:

1,1  1,2  1,3  1,4  ...
2,1  2,2  2,3  2,4  ...
3,1  3,2  3,3  3,4  ...
4,1  4,2  4,3  4,4  ...
...

and then iterating over them along the diagonals, starting from the top
corner. That's just what I'm after, and I have this function that works
for 2-tuples:

def cantor(start=0):
 """Yield coordinate pairs using Cantor's Pairing Function.

 Yields coordinate pairs in (Z*,Z*) over the diagonals:

 >>> it = cantor()
 >>> [next(it) for _ in range(10)]
 [(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3)]

 If ``start`` is given, it is used as the first x- and y-coordinate.
 """
 i = start
 while True:
 for j in range(start, i+1):
 yield (i-j+start, j)
 i += 1


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.

Clearly I'm having a "cannot brain today" moment.

Can anyone help me out here?

Think about the totals of each triple. You'll get totals of 3, then 
totals of 4, etc.


This might help, although the order they come out might not be what you 
want:


def triples():
for total in itertools.count(1):
for i in range(1, total):
for j in range(1, total - i):
yield i, j, total - (i + j)
--
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[Chris Angelico]

On Sat, Mar 10, 2018 at 12:13 PM, Steven D'Aprano
 wrote:
> The Russian mathematician Cantor came up with a *pairing function* that
> encodes a pair of integers into a single one. For example, he maps the
> coordinate pairs to integers as follows:
>
> 1,1  ->  1
> 2,1  ->  2
> 1,2  ->  3
> 3,1  ->  4
> 2,2  ->  5
>
> and so forth. He does this by writing out the coordinates in a grid:
>
> 1,1  1,2  1,3  1,4  ...
> 2,1  2,2  2,3  2,4  ...
> 3,1  3,2  3,3  3,4  ...
> 4,1  4,2  4,3  4,4  ...
> ...
>
> and then iterating over them along the diagonals, starting from the top
> corner.

The diagonals all have a constant sum. You catch the item with a sum
of 2, and then the two with a sum of 3, then the three with a sum of
4, etc. Can that pattern be extended to three dimensions?

(1, 1, 1)
(1, 1, 2) (1, 2, 1) (2, 1, 1)
(1, 1, 3) (1, 2, 2) (1, 3, 1) (2, 1, 2) (2, 2, 1) (3, 1, 1)
etc

Not sure if that helps or not.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Enumerating all 3-tuples

[bartc]

On 10/03/2018 01:13, Steven D'Aprano wrote:

I am trying to enumerate all the three-tuples (x, y, z) where each of x,
y, z can range from 1 to ∞ (infinity).

This is clearly unhelpful:

for x in itertools.count(1):
 for y in itertools.count(1):
 for z in itertools.count(1):
 print(x, y, z)

as it never advances beyond x=1, y=1 since the innermost loop never
finishes.

Georg Cantor to the rescue! (Well, almost...)

https://en.wikipedia.org/wiki/Pairing_function

The Russian mathematician Cantor came up with a *pairing function* that
encodes a pair of integers into a single one. For example, he maps the
coordinate pairs to integers as follows:

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

and so forth. He does this by writing out the coordinates in a grid:

1,1  1,2  1,3  1,4  ...
2,1  2,2  2,3  2,4  ...
3,1  3,2  3,3  3,4  ...
4,1  4,2  4,3  4,4  ...
...

...

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   ...
...



I can't see the patterns here that I can see in the 2-D grid (where the 
first number in each pair in the n'th row is n, and the second number in 
the n'th column is n).


Maybe it needs to be 3-D? (Eg if the 3rd number in the triple is the 
Plane number, then plane 1 looks like:


  1,1,1   1,2,1   1,3,1
  2,1,1   2,2,1   2,3,1
  3,1,1   3,2,1   3,3,1 ...
  ...

But whether that has an equivalent traversal path like the diagonals of 
the 2-D, I don't know. I'm just guessing.)


--
bartc
--
https://mail.python.org/mailman/listinfo/python-list

Enumerating all 3-tuples

[Steven D'Aprano]

I am trying to enumerate all the three-tuples (x, y, z) where each of x, 
y, z can range from 1 to ∞ (infinity).

This is clearly unhelpful:

for x in itertools.count(1):
for y in itertools.count(1):
for z in itertools.count(1):
print(x, y, z)

as it never advances beyond x=1, y=1 since the innermost loop never 
finishes.

Georg Cantor to the rescue! (Well, almost...)

https://en.wikipedia.org/wiki/Pairing_function

The Russian mathematician Cantor came up with a *pairing function* that 
encodes a pair of integers into a single one. For example, he maps the 
coordinate pairs to integers as follows:

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

and so forth. He does this by writing out the coordinates in a grid:

1,1  1,2  1,3  1,4  ...
2,1  2,2  2,3  2,4  ...
3,1  3,2  3,3  3,4  ...
4,1  4,2  4,3  4,4  ...
...

and then iterating over them along the diagonals, starting from the top 
corner. That's just what I'm after, and I have this function that works 
for 2-tuples:

def cantor(start=0):
"""Yield coordinate pairs using Cantor's Pairing Function.

Yields coordinate pairs in (Z*,Z*) over the diagonals:

>>> it = cantor()
>>> [next(it) for _ in range(10)]
[(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3)]

If ``start`` is given, it is used as the first x- and y-coordinate.
"""
i = start
while True:
for j in range(start, i+1):
yield (i-j+start, j)
i += 1


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.

Clearly I'm having a "cannot brain today" moment.

Can anyone help me out here?



-- 
Steve

-- 
https://mail.python.org/mailman/listinfo/python-list