3.3.1 Establishing a bijection between tuples and integers

Consider p domains D_1 through D_p. Each domain D_\ell has cardinality 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:

&(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)\\
+&(i_{p-1}-1)\times n_p\\

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

[&n_2\times n_3\times\cdots\times n_p&\\
&n_3\times\cdots\times n_p&\\

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
      {Nth Dom Q+1}|{DecodeInt R Divs Doms}

1. actually we can recover this distinction easily as explained in Section 3.6.

Denys Duchier
Version 1.2.0 (20010221)