3.3.1 Establishing a bijection between tuples and integers

Consider domains D_1 through D_p . Each domain $D_\ell$ has cardinality $n_\ell$ :

$D_\ell=\{v^\ell_1,\ldots,v^\ell_{n_\ell}\}$

The cardinality of the cartesian product $D_1\times\cdots\times D_p$ is $N=n_1\times\cdots\times n_p$ . We are going to establish a bijection between $D_1\times\cdots\times D_p$ and $[1.\,.N]$ .

The idea is to partition the interval $[1.\,.N]$ into n_1 equal subintervals: one for each value in D_1 . Then to partition each subinterval into n_2 subsubintervals: one for each value in D_2 . Etc recursively.

It is easy to capture this idea in a formula. Consider a tuple $(v^1_{i_1},v^2_{i_2},\ldots,v^p_{i_p})$ . According to the recursive algorithm outlined above, it is assigned to the following integer:

$\begin{array}{ll} &(i_1-1)\times(n_2\times n_3\times\cdots\times n_p)\\ +&(i_2-1)\times(n_3\times\cdots\times n_p)\\ \vdots&\\ +&(i_{p-1}-1)\times n_p\\ +&(i_p-1)\\ +&1 \end{array}$

Thus, given an index in the range $[1.\,.N]$ , we can recover the corresponding tuple by calling {DecodeInt I-1 Divs Doms}, where Divs is the list:

$\begin{array}{r@{}r@{}l} [&n_2\times n_3\times\cdots\times n_p&\\ &n_3\times\cdots\times n_p&\\ \multicolumn{3}{c}{\vdots}\\ &n_p&\\ &1&] \end{array}$

and Doms is the list of domains, each one consisting of a list of values. The function DecodeInt is implemented as follows:

<DomainProduct DecodeInt function>=: fun {DecodeInt I Divs Doms} case Divs#Doms of nil#nil then nil [] (Div|Divs)#(Dom|Doms) then Q = I div Div R = I mod Div in {Nth Dom Q+1}|{DecodeInt R Divs Doms} end end