### 3.3.1 Establishing a bijection between tuples and integers

Consider domains through . Each domain has cardinality :

The cardinality of the cartesian product is . We are going to establish a bijection between and .

The idea is to partition the interval into equal subintervals: one for each value in . Then to partition each subinterval into subsubintervals: one for each value in . Etc recursively.

It is easy to capture this idea in a formula. Consider a tuple . According to the recursive algorithm outlined above, it is assigned to the following integer:

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

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

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

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

Denys Duchier
Version 1.2.0 (20010221)