Counting All Tuples

In math, the positive integers 1, 2, 3, ... are the quintessential countable set. To show that another set is countable you have to pair up its elements with the positive integers without missing anything. In other words, you need to list the elements of the set with no infinite gaps. Otherwise the set is uncountable like the real numbers.

For example, the positive even integers 2, 4, 6, ... are countable because they can easily be listed with no gaps and have an obvious pairing with the positive integers : 1→2, 2→4, 3→6, ....

In this post I’ll be considering tuples of positive integers of any non-negative integer length n, such as (5,5) or (1,2,3,4), and showing how they too are countable, even though there are infinitely many tuple lengths n, and infinitely many tuples of each length (except n=0). I’ll also be writing Python code to list thousands of them.

It won’t make sense yet but their list goes:

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

Counting 2-Tuples

The classic starting point is to show that ordered pairs (2-tuples) of positive integers like (1,1) or (2,3) are countable. A way to do this is to treat each pair as an (x,y) point on a grid and draw successive diagonals down and left from every (x,1) point to the corresponding (1,y) point:

y\x   1     2     3     4     5     6
1   (1,1) (2,1) (3,1) (4,1) (5,1)  ...
         /     /     /     / 
2   (1,2) (2,2) (3,2) (4,2)
         /     /     /
3   (1,3) (2,3) (3,3)
         /     /
4   (1,4) (2,4)
         /    
5   (1,5)

6   ...

Then list the diagonals out from shortest to longest, so the sequence is (1,1), (2,1), (1,2), (3,1), (2,2), (1,3), (4,1), ... and we have shown 2-tuples are countable. This corresponds to a 1-indexed Cantor pairing function, which can be implemented in Python as:

def cantor_pairing(k1, k2):
    return (k1 + k2) * (k1 + k2 + 1) // 2 + k2

def xy_pairing(x, y):
    return cantor_pairing(x - 1, y - 1) + 1

print(xy_pairing(1, 1))  # -> 1
print(xy_pairing(2, 1))  # -> 2
print(xy_pairing(1, 2))  # -> 3
print(xy_pairing(3, 1))  # -> 4

The common proof that rational numbers are countable follows from this fact that ordered pairs are.

Counting N-Tuples

Now where it gets interesting is that you can view the x or y sequence of positive integers used above for the grid axes as any other countable sequence – we know they can map to each other after all by definition.

For example, replace y with the sequence of 2-tuples just described and repeat the same (x,y) diagonalization:

y\x          1         2         3         4
1=(1,1)   (1,(1,1)) (2,(1,1)) (3,(1,1))  ...
                   /         /         /
2=(2,1)   (1,(2,1)) (2,(2,1)) (3,(2,1))  ...
                   /         /         /
3=(1,2)   (1,(1,2)) (2,(1,2)) (3,(1,2))
                   /         /
4=(3,1)        ...        ...

The (x,y) pairs start to feel like Lisp-style lists and can be compressed to 3-tuples. So the order goes (1,1,1), (2,1,1), (1,2,1), (3,1,1), ... and we have shown that 3-tuples are countable.

The crucial point now is that this could be repeated again. Replace y with the sequence of 3-tuples and we get countable 4-tuples. Do it again for countable 5-tuples, etc. For any n, the set of n-tuples of positive integers is countable!

(I never actually mentioned 0-tuples or 1-tuples but there is only one 0-tuple () and the sequence for 1-tuples (1), (2), (3),... is obvious, so they are both countable.)

Counting All N-Tuples

Finally, what’s fascinating is you can show that all n-tuples for all values of n combined are countable. Let Tn_k be the kth n-tuple and arrange each countable sequence of n-tuples on its own column of a grid:

k\n   1    2    3    4    5
  T1_1 T2_1 T3_1 T4_1 ...

  T1_2 T2_2 T3_2 T4_2

  T1_3 T2_3 T3_3 T4_3 

  T1_4 T2_4 T3_4 T4_4

  ...

Then list off the diagonals just like before for a countable sequence of all n-tuples for all positive n:

T1_1, T2_1, T1_2, T3_1, T2_2, T1_3, T4_1, ...

Which works out to these actual tuples:

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

Tack the empty tuple () on the front for the sake of completeness.

Thus, a combination of infinitely many infinite sets is in fact countable! This is not always true but works here because the sets are countable and there are countably many of them.

Coding It

The goal now is to write some Python 3 code that actually generates the infinite sequences of n-tuples described above.

0-Tuples and 1-Tuples

It starts off easy with 0-tuples and 1-tuples.

The empty tuple is the only 0-tuple so we can have a generator that yields it and does nothing else:

def zero_tuples():
    """Finite generator over all 0-tuples, namely ()."""
    yield ()

print(list(zero_tuples()))  # -> [()]

For 1-tuples we can make an endless generator by repeatedly yielding and incrementing a value:

def one_tuples(start=1):
    """Infinite generator over all 1-tuples (start+k,) for k=0,1,2,3,..."""
    while True:
        yield start,
        start += 1

Note the comma in yield start, makes it yield a one-element tuple rather than the integer start.

Here, since the generator is infinite, list(one_tuples()) would never finish, but we can zip with a bounded range or take an iterator slice to see some output:

for _, t in zip(range(5), one_tuples()):
    print(t, end=' ')  # -> (1,) (2,) (3,) (4,) (5,)

from itertools import islice
print(list(islice(one_tuples(), 5)))  # -> [(1,), (2,), (3,), (4,), (5,)]

Combining Into N-Tuples

To make sequences of 2-tuples and beyond we need a way to combine two infinite generators with the diagonalization method described above.

The following combine function does just that. It maintains two lists corresponding to the elements of the x and y axes of the grid. It generates the lists from the generators as needed with the internal get_index function. It carefully indexes the lists in the for loop to get the current (x,y) that are combined with combiner, which by default adds so it concatenates tuples. The entire lists need to be kept in memory since every diagonal references everything in both lists up to that point.

def combine(x_generator, y_generator, combiner=lambda x, y: x + y):
    """Combines two infinite generators into one by arranging them in a grid
       and taking diagonals in the same way as the Cantor pairing function."""
    def get_index(lst, gen, index):
        if index == len(lst):
            lst.append(next(gen))
        return lst[index]
    x_list, y_list = [], []
    diagonal = 1
    while True:
        for y_index in range(diagonal):
            x_index = diagonal - y_index - 1
            x = get_index(x_list, x_generator, x_index)
            y = get_index(y_list, y_generator, y_index)
            yield combiner(x, y)
        diagonal += 1

Combining one_tuples with itself gives the sequence of 2-tuples we expect:

for _, t in zip(range(5), combine(one_tuples(), one_tuples())):
    print(t, end=' ')  # -> (1, 1) (2, 1) (1, 2) (3, 1) (2, 2)

But of course the goal is to be able to produce n-tuple generators for any n. The n_tuples function does this recursively in one line by combining one_tuples() with the next smaller n-tuple:

def n_tuples(n):
    """Returns generator over n-tuples of positive integers for int n > 0."""
    return one_tuples() if n == 1 else combine(one_tuples(), n_tuples(n-1))

An iterative version is also possible:

def n_tuples_iterative(n):
    """Returns generator over n-tuples of positive integers for int n > 0."""
    generator = one_tuples()
    for _ in range(n - 1):
        generator = combine(one_tuples(), generator)
    return generator

For n = 3, n_tuples generates the sequence of 3-tuples we expect:

for _, t in zip(range(5), n_tuples(3)):
    print(t, end=' ')  # -> (1, 1, 1) (2, 1, 1) (1, 2, 1) (3, 1, 1) (2, 2, 1)

Diagonalizing Into All Tuples

The final stage is to do the diagonalization step from above where all n-tuples are arranged on the grid. The function all_tuples does this and works in much the same way as combine did. It maintains a 2D list of the grid and adds to it as needed, either by getting the next item of a generator with Python’s next built-in, or creating the generators in the first place with n_tuples.

For completeness, zero_tuples is brought back in to supply the empty tuple.

def all_tuples():
    """Infinite generator over all n-tuples of positive integers for all n."""
    yield from zero_tuples()
    lists, generators = [], []
    diagonal = 1
    while True:
        for y_index in range(diagonal):
            x_index = diagonal - y_index - 1
            if x_index == len(lists):
                generators.append(n_tuples(diagonal))
                lists.append([])
            if y_index == len(lists[x_index]):
                lists[x_index].append(next(generators[x_index]))
            yield lists[x_index][y_index]
        diagonal += 1

A nicely formatted list of all tuples can be made with a little help from this function:

def print_all_tuples(stop_at=99):
    places = len(str(stop_at))
    for i, t in zip(range(stop_at + 1), all_tuples()):
        print(f"{i:>{places}} ({','.join(map(str, t))})")

So print_all_tuples(15) outputs:

()
(1)
(1,1)
(2)
(1,1,1)
(2,1)
(3)
(1,1,1,1)
(2,1,1)
(1,2)
(4)
(1,1,1,1,1)
(2,1,1,1)
(1,2,1)
(3,1)
(5)

Here is the output of the first ten-thousand tuples (print_all_tuples(10000)). It is mostly ones and tuple values grow rather slowly since there are so many to enumerate. Tuple (5,5) is all the way at index 902. But in theory, given enough time (and setting sys.setrecursionlimit high) any n-tuple of positive integers you can think of will appear in the output!

Ending Notes

The full source code of this blog post is available on my GitHub.

I recommend these excellent Veritasium and Numberphile videos to learn more about countability and infinities: