Introduction
Some programming languages supply an interleave method for combining elements from infinite lists. The usual pattern for this is cycling through the set of lists, taking successive elements. When combination as a tuple is required, however, the problem becomes more complex, because of the need to ensure that every combination of elements is visited. Walking all combinations of finite lists is straightforward; it is possible to chain lists together and use an increment-and-carry method. This approach is unsuitable for infinite lists, as the first list to be incremented would never carry. It is thus necessary to weave the lists together without getting trapped in infinity.
We consider only indexed, random-access lists (that is, lists where the cost of fetching an element by its index is the same regardless of the index). For example, a list of the Fibonacci Sequence generated using a recursive method would not be suitable (regardless of the method of recursion), but the Fibonacci Sequence generated by Binet’s Formula would be acceptable. We also wish to be able to subdivide the walk of combinations in a parallelisable and state-recoverable manner (that is, we wish to be able to describe ranges of the walk in such a way that the walk can be started or continued from that point, without overlapping with unwanted combinations); thus, we do not consider methods employing nested interleaves. We show that is is possible to satisfy these properties and walk all combinations of infinite lists in a dense manner.
Reduction to 2 lists
We call our walk \( W \) and represent the first combination walked as \( W_1 \), which will represent some address \( (A_x, B_y) \) where \( x, y \) are the indexes to be determined. The walked combinations are thus \( W_1, W_2, \ldots \). Note \( x, y \in \mathbb{N} \) (from which we always exclude \( 0 \)). We name the elements of List \( L \) \( [L_1, L_2, \ldots] \). Note that we use unity-indexing throughout.
It is sufficient to walk all combinations of only two infinite lists. That is because multiple lists can be combined in a binary tree, satisfying the required properties. For example, consider Lists \( A \), \( B \), \( C \). Suppose it is possible to walk combinations of \( A \) and \( B \); then it is possible to combine these lists as List \( AB \), where \( AB_1 \) addresses the first combination from Lists \( A \) and \( B \) (similar to how we use \( W \) to represent our overall walk). We then walk Lists \( AB \) and \( C \). (This means we walk lists at different speeds for more than 2 lists, because of the binary tree. However, the walk is still dense and satisfies the required properties.)
With lists combined in this way, we consider only walking all combinations of 2 infinite lists.
Method for 2 lists
We claim the following satisfies the required properties for walking all combinations of 2 infinite Lists X and Y, defining the formulas thusly for subsequent convenience:
\begin{array}{rcl} m(n) & = & \left \lceil \frac{1 + \sqrt{1 + 8n}}{2} \right \rceil \newline x(n) & = & n - \frac{(m(n) - 1)(m(n) - 2)}{2} \newline y(n) & = & m(n) - x(n) \newline & where \newline n & \in & \mathbb{N} \end{array}
Using these formulas, we define the required function:
\begin{array}{rcl} f & : & \mathbb{N} \to \mathbb{Z}^2 \newline n & \mapsto & \left( x(n), y(n) \right) \end{array}
We show that the image of \( f \) is in fact \( \mathbb{N}^2 \), that \( f \) is both injective and surjective, and hence that \( f \) is bijective \( \mathbb{N} \to \mathbb{N}^2 \). This is so we can walk \( \mathbb{N} \), using \( x(n) \) as the index in List X, and \( y(n) \) as the index in List Y.
Image of \( f \)
\( \forall n \in \mathbb{N} \), \( m(n) \in \mathbb{Z} \). Thus, \( x(n) \in \mathbb{Z} \) since the fraction is odd times even. Thus, \( y(n) \in \mathbb{Z} \). We seek to show that \( x(n), y(n) \geq 1 \), meaning \( x(n), y(n) \in \mathbb{N} \) and thus the image of \( f \) is \( \mathbb{N}^2 \).
Let us define the subsets of \( \mathbb{N} \):
\begin{array}{rcl} S_t & := & \left\lbrace n \in \mathbb{N} : \frac{(t - 1)(t - 2)}{2} < n \leq \frac{t(t - 1)}{2} \right\rbrace \newline & for \newline t & \in & \mathbb{N} \setminus \lbrace 1 \rbrace \end{array}
For example, \( S_2 = \lbrace 1 \rbrace \), \( S_3 = \lbrace 2, 3 \rbrace \), \( S_4 = \lbrace 4, 5, 6 \rbrace \), etc. We note \( S_2 \cup S_3 \cup S_4 \cup \dots = \mathbb{N} \), thus \( S_t \) partitions \( \mathbb{N} \). We observe that by construction, each \( S_t \) contains precisely one triangle number.
We consider what happens when we put a triangle number into \( m \):
\begin{array}{rcl} m\left( \frac{t(t - 1)}{2} \right) & = & \left \lceil \frac{1 + \sqrt{1 + 8\left( \frac{t(t - 1)}{2} \right)}}{2} \right \rceil \newline & = & \left \lceil \frac{1 + \sqrt{4\left( t - \frac{1}{2} \right)^2}}{2} \right \rceil \newline & = & \left \lceil \frac{1 + 2 \left( t - \frac{1}{2} \right)}{2} \right \rceil \newline & = & \lceil t \rceil \newline & = & t \end{array}
We observe that \( m \) is non-strict increasing, since \( \forall n \in \mathbb{N} \):
\begin{array}{rcl} \frac{1 + \sqrt{1 + 8(n + 1)}}{2} & > & \frac{1 + \sqrt{1 + 8n}}{2} \end{array}
and since \( a < b \implies a < \lceil b \rceil \implies \lceil a \rceil \leq \lceil b \rceil \)
\begin{array}{rcl} \left \lceil \frac{1 + \sqrt{1 + 8(n + 1)}}{2} \right \rceil & \geq & \left \lceil \frac{1 + \sqrt{1 + 8n}}{2} \right \rceil \newline & \implies \newline m(n+1) & \geq & m(n) \end{array}
We next take an arbitrary \( s \in S_t \), and consider \( m(s) \). By the construction of \( S_t \):
\begin{array}{rcl} \frac{(t - 1)(t - 2)}{2} & < s & \leq \frac{t(t - 1)}{2} \newline & \implies \newline m \left( \frac{(t - 1)(t - 2)}{2} \right) & \leq m(s) & \leq m \left( \frac{t(t - 1)}{2} \right) \end{array}
since \( m \) non-strict increasing, thus \( t - 1 \leq m(s) \leq t \). But \( m(s) \in \mathbb{Z} \), so \( m(s) \in \lbrace t - 1, t \rbrace \).
We seek to exclude \( m(s) = t - 1 \). Let us imagine such a value is fine, and reach a contradiction.
\begin{array}{rcl} m(s) & = & \left \lceil \frac{1 + \sqrt{1 + 8s}}{2} \right \rceil \newline & \iff \newline m(s) - 1 & < \frac{1 + \sqrt{1 + 8s}}{2} & \leq m(s) \newline & \implies \newline t - 2 & < \frac{1 + \sqrt{1 + 8s}}{2} & \leq t - 1 \newline & \implies \newline 2(t - 2) - 1 & < \sqrt{1 + 8s} & \leq 2(t - 1) - 1 \newline & \implies \newline (2t - 5)^2 & < 1 + 8s & \leq (2t - 3)^2 \newline & \implies \newline \frac{(2t - 5)^2 - 1}{8} & < s & \leq \frac{(2t - 3)^2 - 1}{8} \newline & \implies \newline \frac{1}{2}t^2 - \frac{5}{2}t + 3 & < s & \leq \frac{1}{2}t^2 - \frac{3}{2}t + 1 \newline & \implies \newline \frac{(t - 2)(t - 3)}{2} & < s & \leq \frac{(t - 1)(t - 2)}{2} \end{array}
But by construction of \( S_t \), \( \frac{(t - 1)(t - 2)}{2} < s \leq \frac{t(t - 1)}{2} \), thus \( s < s \) and we reach a contradiction.
Thus, \( m(s) \in \lbrace t \rbrace \) so \( m(s) = t \). Thus, for any \( s \in S_t \), \( m(s) = t \). This means that by partitioning \( \mathbb{N} \) in this manner, we can consider each \( S_t \) within which \( m(s) \) is constant and the ceiling function no longer makes us anxious.
We now show that \( x(n), y(n) \geq 1 \). Instead of trying to show this directly, we show that it is true within every \( S_t \). But since that partitions \( \mathbb{N} \), it yields the required result.
Take \( s \in S_t \). By construction of \( S_t \):
\begin{array}{rcl} s & > & \frac{(t - 1)(t - 2)}{2} \newline & \implies \newline s - \frac{(t - 1)(t - 2)}{2} & > & 0 \newline & \implies \newline s - \frac{(t - 1)(t - 2)}{2} & \geq & 1 \newline & \implies \newline x(s) & \geq & 1 \end{array}
meaning every element in \( S_t \) is strict positive, so \( x(n) \geq 1 \forall n \in \mathbb{N} \).
Similarly, take \( s \in S_t \). By construction of \( S_t \):
\begin{array}{rcl} s & \leq & \frac{t(t - 1)}{2} \newline & = & \left( \frac{t(t - 1)}{2} + 1 \right) - 1 \newline & = & \left( \frac{(t - 1)(t - 2)}{2} + t \right) - 1 \newline & \leq & \frac{(m(s) - 1)(m(s) - 2)}{2} + m(s) - 1 \newline & \implies \newline 1 & \leq & m(s) - s + \frac{(m(s) - 1)(m(s) - 2)}{2} \newline & = & y(s) \end{array}
meaning every element in \( S_t \) is strict positive, so \( y(n) \geq 1 \forall n \in \mathbb{N} \).
Since we already know \( f : \mathbb{N} \to \mathbb{Z}^2 \), we observe that the image is in fact \( \mathbb{N}^2 \), so we can redefine \( f : \mathbb{N} \to \mathbb{N}^2 \) and say that the image and the codomain are the same.
Injectivity of \( f \)
Choose \( (x_1, y_1) \in \mathbb{N}^2 \) according to \( f \) for some \( n_1 \in \mathbb{N} \) such that:
\begin{array}{rcl} m_1 & = & \left \lceil \frac{1 + \sqrt{1 + 8n_1}}{2} \right \rceil \newline x_1 & = & n_1 - \frac{(m_1 - 1)(m_1 - 2)}{2} \newline y_1 & = & m_1 - x_1 \end{array}
Choose \( (x_2, y_2) \in \mathbb{N}^2 \) in a similar manner for some \( n_2 \in \mathbb{N} \). Suppose \( (x_1, y_1) = (x_2, y_2) \). Then \( x_1 = x_2 \) and \( y_1 = y_2 \).
Substituting, \( y_2 = m_1 - x_2 \). Since \( y_2 = m_2 - x_2 \), \( m_1 = m_2 \).
Also substituting, \( x_1 = n_2 - \frac{(m_2 - 1)(m_2 - 2)}{2} = n_2 - \frac{(m_1 - 1)(m_1 - 2)}{2} \). Since \( x_1 = n_1 - \frac{(m_1 - 1)(m_1 - 2)}{2} \), \( n_1 = n_2 \).
Thus \( f \) is injective.
Surjectivity of \( f \)
Choose arbitrary \( (x_1, y_1) \in \mathbb{N}^2 \). We seek \( n_1 \in \mathbb{N} \) such that \( f \) is satisfied; that is:
\begin{array}{rcl} m(n_1) & = & \left \lceil \frac{1 + \sqrt{1 + 8n_1}}{2} \right \rceil \newline x_1 = x(n_1) & = & n_1 - \frac{(m(n_1) - 1)(m(n_1) - 2)}{2} \newline y_1 = y(n_1) & = & m(n_1) - x(n_1) \end{array}
It might seem straightforward to substitute and solve for \( n_1 \) explicitly, then calculate \( m(n_1) \) explicitly, then show that \( x(n_1) = x_1 \) and \( y(n_1) = y_1 \). In this form, however, dancing with the ceiling function is tricksy. Instead, we view the problem as a system of constraints and rewrite it into a simpler form, finding \( n_1 \) along the way.
\begin{array}{rcl} m(n_1) & = & \left \lceil \frac{1 + \sqrt{1 + 8n_1}}{2} \right \rceil \newline x_1 & = & n_1 - \frac{(m(n_1) - 1)(m(n_1) - 2)}{2} \newline y_1 & = & m(n_1) - x_1 \end{array}
and substituting \( m(n_1) \) throughout:
\begin{array}{rcl} x_1 + y_1 & = & \left \lceil \frac{1 + \sqrt{1 + 8n_1}}{2} \right \rceil \newline x_1 & = & n_1 - \frac{(x_1 + y_1 - 1)(x_1 + y_1 - 2)}{2} \end{array}
and rewriting the ceiling function as an inequality and rearranging:
\begin{array}{lcl} x_1 + y_1 - 1 < \frac{1 + \sqrt{1 + 8n_1}}{2} \leq x_1 + y_1 \newline n_1 = x_1 + \frac{(x_1 + y_1 - 1)(x_1 + y_1 - 2)}{2} \end{array}
Considering the inequality:
\begin{array}{lcl} x_1 + y_1 - 1 < \frac{1 + \sqrt{1 + 8n_1}}{2} \leq x_1 + y_1 \newline \implies 2(x_1 + y_1) - 3 < \sqrt{1 + 8n_1} \leq 2(x_1 + y_1) - 1 \newline \implies \left\lbrack 2(x_1 + y_1) - 3 \right\rbrack^2 < 1 + 8n_1 \leq \left\lbrack 2(x_1 + y_1) - 1 \right\rbrack^2 \newline \implies \frac{\left\lbrack 2(x_1 + y_1) - 3 \right\rbrack^2 - 1}{8} < n_1 \leq \frac{\left\lbrack 2(x_1 + y_1) - 1 \right\rbrack^2 - 1}{8} \newline \implies \frac{ 4(x_1 + y_1)^2 - 12(x_1 + y_1) + 8}{8} < n_1 \leq \frac{ 4(x_1 + y_1)^2 - 4(x_1 + y_1) }{8} \newline \implies \frac{1}{2}(x_1 + y_1)^2 - \frac{3}{2}(x_1 + y_1) + 1 < n_1 \leq \frac{1}{2}(x_1 + y_1)^2 - \frac{1}{2}(x_1 + y_1) \end{array}
Considering the equality:
\begin{array}{rcl} n_1 & = & x_1 + \frac{(x_1 + y_1 - 1)(x_1 + y_1 - 2)}{2} \newline & = & x_1 + \frac{1}{2}(x_1 + y_1)^2 - \frac{3}{2}(x_1 + y_1) + 1 \end{array}
Thus we can rewrite the system as:
\begin{array}{lcl} \frac{1}{2}(x_1 + y_1)^2 - \frac{3}{2}(x_1 + y_1) + 1 < n_1 \leq \frac{1}{2}(x_1 + y_1)^2 - \frac{1}{2}(x_1 + y_1) \newline n_1 = x_1 + \frac{1}{2}(x_1 + y_1)^2 - \frac{3}{2}(x_1 + y_1) + 1 \end{array}
and multiplying by \( 2 \) and substituting \( n_1 \):
\begin{array}{lcl} (x_1 + y_1)^2 - 3(x_1 + y_1) + 2 < 2x_1 + (x_1 + y_1)^2 - 3(x_1 + y_1) + 2 \leq (x_1 + y_1)^2 - (x_1 + y_1) \end{array}
We now split the inequality. The LHS simplifies to \( 0 < x_1 \implies 1 \leq x_1 \) which we know to be true. The RHS simplifies to \( x_1 - (x_1 + y_1) + 1 \leq 0 \implies -y_1 \leq -1 \implies y_1 \geq 1 \) which we know to be true.
So our candidate solution to the system, which must be unique if so, is:
\begin{array}{rcl} n_1 = x_1 + \frac{(x_1 + y_1 - 1)(x_1 + y_1 - 2)}{2} \end{array}
which was fairly clear at the beginning, but we have shown it satisfies all the constraints including the ceiling. Clearly, \( n_1 \in \mathbb{Z} \) since the fraction is even times odd. But \( x_1, y_1 \geq 1 \implies x_1 + y_1 \geq 2 \implies n_1 \geq 1 \), so \( n_1 \in \mathbb{N} \).
Thus, we have found \( n_1 \in \mathbb{N} \) which satisfies the constraints and this \( n_1 \mapsto (x_1, y_1) \), which was an arbitrary choice in \( \mathbb{N}^2 \). Thus \( f \) is surjective.
Conclusion
Since \( f : \mathbb{N} \to \mathbb{N}^2 \) is both injective and surjective, it is bijective. We have also found explicit ways of converting between \( \mathbb{N} \) and \( \mathbb{N}^2 \) in either direction. This \( f \) satisfies the properties we required for walking all combinations of infinite Lists X and Y. We make ourselves anxious about the holes and mistakes in our argument, hope they are not too serious, and finish off the coffee.