A method to found bijections from a set of n integers to {0,1, ... ,n-1}
------------------------------------------------------------------------

1. The method
-------------

   A simple method to generate functions from a set of n integers

A = {i_1, i_2, ... ,i_n} to the set B = {0,1, ... , n-1},

is to compute the values of

i_1 mod I mod n,
i_2 mod I mod n,
      ...      ,
i_n mod I mod n;

for I = minI, minI+2, ... ,10^7-1, and I = minI+1, minI+3, ... , 10^7; where

minI = n^3, if n is odd, and minI = n^3+1, if n is even. In this way we limit
the search to less than 10^7 functions, and first test odd values of I.

   If we found I such that the values of I_j mod I mod n are distinct, j=1,...,
n; we stop with success. If not we  fail.

   In case of success, we make a table T once. We will use T every time we want
to know if a given positive integer x belongs or not to the set A. We generate
table T with n entries, storing I_j at T[I_j mod I mod n], j=1, ... ,n. In this
way x belongs to A if T[x mod I mod n] = x. Also x is not an element of A, if
T[x mod I mod n] is not equal to x.
   The next section is about the probability of  pick a bijection f "at random".

2. On the probability of pick a bijection f "at random"
-------------------------------------------------------

   Given sets A, B with n elements, the probability P(n) to found a function
f:A->B at random, f a bijection, is given by

(1) P(n) = n!/n^n

   (1) is true because there are n^n distinct functions or sequences on n
symbols of length n.  Note that  n! of those sequences, have n distinct symbols.

Example 1. If n = 1, f is always a bijection and P(n) = 1!/1^1 = 1.

Example 2. For n = 2, let

A = {x,y}, and
B = {X,Y}.

   The possibilities are

f(x)=X, f(y)=X, so we have the correspondent sequence X,X
f(x)=X, f(y)=Y,                       "               X,Y
f(x)=Y, f(y)=Y,                       "               Y,Y
f(x)=Y, f(y)=X,                       "               Y,X.

The probability is 0.5 since there are 2 bijections in a total of 4 cases.
---

   P(n) decreases very quickly as n increases. For n = 13, P(n) = 0.00002056.
For n = 17, P(n) = 0.00000043. This means that on the average we have to try
1/P(13) or 48,638 functions to found a bijection for a set of 13 values. When n
is 17, one can expect to try 2,325,751 functions. (See A209082)
   From examples in the next section, it is reasonable to consider this method
equivalent to generate functions at random. So one can use the algorithm with
success for sets with 17 or less values.

3. How good is the method? (functions of form x mod I mod n vs. "random functions")
----------------------------------------------------------------------------------

      We will see two examples, (more examples could be better) that shows that
those functions have characteristics similar to "random functions".

Ex 1. Set A equal to the first 13 terms of OEIS sequence A056915. (See A208846.)

   In this case, the bijection is A056915[n] mod 76057 mod 13, the algorithm
generates 36,931 functions. The expected value of number of functions 1/P(13) is
48,638. The average of the number of points in the images of the generated
functions was 6.283. The theoretical value, see A209081, is a value between 8
and 9. Execution time was 0.047 seconds.
---

Ex 2. Set A equal to the first 17 terms of OEIS sequence A056915. (See A208847.)

   In this case, the bijection is A056915[n] mod 5228905 mod 17, the algorithm
generates 2,611,997 functions. The expected value 1/P(17) is 2,325,751. The
average of the number of points in the images of the generated functions was
9.12. The expected value, see A209081, is a value between 10 and 11. Execution
time was 0.749 seconds.

Ex 3. Set A equal to the first 18 terms of OEIS sequence A056915.
   The method fails in this case. Number of tested functions 9,994,168
execution time was 2.886 seconds. 


   In example 1, the experimental average of the cardinalities of the images,
6.283, is small compared with the expected value. This probably occurs because
we test only "small" values of I. Udi Manber, [1], inspired me to use functions
of form x mod I mod n. He discuss those functions in another context and
advocates the parameter I not so small. Considering the weakness of this method
for domains with small numbers, I choose to begin with n^3 because if i_j in A
is less than I, the expression i_j mod I mod n is equal to i_j mod n.

   The code below assumes global declarations of the domain A of the bijection to
found, and the cardinality n of A. A is represented by a table A[0],A[1], ... ,
A[n-1]. See declarations below. If you want to experiment with other domains, only
change the values of table A, and n.

4. C code
---------

#include <iostream>
#include <math.h>
const unsigned int n = 17;
const unsigned long long A[19] = {
25326001,161304001,960946321,1157839381,3215031751,3697278427,5764643587,
6770862367, 14386156093, 15579919981, 18459366157, 19887974881, 21276028621,
27716349961,29118033181, 37131467521, 41752650241, 42550716781, 43536545821};
// A = A056915(1) to A056915(19).

/*
   Function FindBijection() returns true when founds a bijection, and false
otherwise. Parameter I is the intermediary divisor, b = 2^n - 1.           */

inline bool FindBijection(unsigned long long I, unsigned int b){
unsigned int Tbits = 0, j;
for(j = 0; j < n; j++)
   Tbits |= (1ull << (A[j] % I % n)); // Set bit (A[j] % I % n).
if(Tbits == b) // if Tbits = (11...1)2
   return true;
return false;
}

int main(){
unsigned int b = powl(2, n) - 1;    b = 2^n-1
unsigned long long I, k = 0, minI;
bool bijection = false;
if(n % 2 == 1) minI = n*n*n; else minI = n*n*n + 1;
for(I = minI; I <= 10000000ull -1ull; I += 2ull){
   k++;
   if(FindBijection(I, b)){
      bijection = true; break;}
   }
if(!bijection)
   for(I = minI+1; I <= 10000000ull; I += 2ull){
      k++;
      if(FindBijection(I, b)){
         bijection = true; break;}
      }
cout << "n " << n << " ";
if(bijection) {cout<< "I = " << I << endl;
   for(b = 0; b < n; b++)
      cout << A[b] << " " << A[b] % I % n << endl;
   }
else cout<< "Bijection not found.\n";
cout << "Number of tested functions " << k << endl;
return 0;
}
//------

References
----------

[1]Udi Manber, Introduction to Algorithms -- A Creative Approach, Addison-Wesley,
Reading, MA.
OEIS sequences A056915, A208846, A208847, A209081, and A209082.

---------------------------------------------------------------------------------

Output of main() for n = 13
---------------------------
n 13 I = 76057
25326001 2
161304001 7
960946321 11
1157839381 10
3215031751 5
3697278427 9
5764643587 6
6770862367 3
14386156093 4
15579919981 0
18459366157 1
19887974881 12
21276028621 8
Number of tested functions 36931
execution time : 0.047 s
---

Output of main() for n = 17
---------------------------
n 17 I = 5228905
25326001 3
161304001 4
960946321 13
1157839381 15
3215031751 8
3697278427 14
5764643587 9
6770862367 5
14386156093 0
15579919981 11
18459366157 16
19887974881 10
21276028621 2
27716349961 12
29118033181 7
37131467521 1
41752650241 6
Number of tested functions 2611997
execution time : 0.749 s
---

Output of main() for n = 18
---------------------------
n 18 Bijection not found.
Number of tested functions 9994168
execution time : 2.886 s
---------------------------------------------------------------------------------