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