Enumerating all 3-tuples

[Ben Bacarisse]

Ben Bacarisse <ben.usenet at bsb.me.uk> writes:

> Steven D'Aprano <steve+comp.lang.python at pearwood.info> 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).
<snip>

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