A method to find 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, ... ,maxI-1, and I = minI+1, minI+3, ... , maxI; where
minI = n^3, if n is odd, and minI = n^3+1, if n is even;
maxI = 10^7 if n <= 15, or the least member of A is less than 10^9;
maxI = 16 * A055775(n), if 16 <= n <= 19;
maxI = minI+1 if n > 19.
In this way first we test odd values of I, and in the worst csase, i.e., when
n = 19, we test near 16 * A055775(19), or 260,221,856 functions.
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,750 functions. (See A055775)
3. Examples
-----------
We will see seven 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,
A055775(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 A055775(17) is 2,325,750. 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.
Ex 4. Set A equal to the first 14 terms of OEIS sequence A074773. (See A209833)
In this case, the bijection is A074773(n) mod 264029 mod 14, the algorithm
generates 130,643 functions. The expected value A055775(14) is 127,463. The
average of the number of points in the images of the generated functions was
8.71. The expected value, see A209081, is a value between 9 and 10. Execution
time was 0.14 seconds.
Ex 5. Set A equal to the first 18 terms of OEIS sequence A074773. (See A209834)
In this case, the bijection is A074773(n) mod 1519829 mod 18, the algorithm
generates 756,999 functions. The expected value A055775(18) is 6,145,596. The
average of the number of points in the images of the generated functions was
9.593. The expected value, see A209081, is a value between 11 and 12. Execution
time was 0.25 seconds.
Ex 6. Set A equal to the first 19 terms of OEIS sequence A074773.
The method fails in this case. Number of tested functions 260,214,998.
Execution time was 75.74 seconds.
Ex 7. Set A equal to the first 20 terms of OEIS sequence A074773.
The method fails in this case. Number of tested functions 2. Execution time
was less than 0.0001 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.
From the examples above, for sets with 17 or less values, one normally finds
a bijection. For n<=19 it is possible to found a bijection if the least value of
the domain A is greater than 10^9. Example 5 shows a case where we find a
bijection very quickly. On the other hand, in example 6 we fail after try
approx. 16 times the expected value of number of functions.
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
#include
const unsigned int n = 14;
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).
unsigned long long Compute_MaxI(unsigned long long minI){
if((n <= 15)||(A[0] < 1000000000ull)) return 10000000ull;//A[0] the least element of A.
if(n > 19) return minI + 1ull;
if(n == 16) return 16ull * 881657ull; // 16*A055775(16)
if(n == 17) return 16ull * 2325750ull; // 16*A055775(17)
if(n == 18) return 16ull * 6145596ull; // 16*A055775(18)
return 16ull * 16263866ull; // 16*A055775(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, maxI;
bool bijection = false;
if(n % 2 == 1) minI = n*n*n; else minI = n*n*n + 1;
maxI = Compute_MaxI(minI);
for(I = minI; I <= maxI -1ull; I += 2ull){
k++;
if(FindBijection(I, b)){
bijection = true; break;}
}
if(!bijection)
for(I = minI+1; I <= maxI; 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 A055775, A056915, A074773, A208846, A208847, A209081, A209833,
and A209834.
---------------------------------------------------------------------------------
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
---------------------------------------------------------------------------------
Declarations used to run examples 4 to 7.
const unsigned int n = 18;
const unsigned long long A[20]= {//A074773 Strong pseudoprimes to bases 2,3,5,7.
3215031751, 118670087467, 307768373641, 315962312077, 354864744877, 457453568161,
528929554561, 546348519181, 602248359169, 1362242655901, 1871186716981,
2152302898747, 2273312197621, 2366338900801, 3343433905957, 3461715915661,
3474749660383, 3477707481751, 4341937413061, 0};
Output of main() corresponding to ex. 4
---------------------------------------
n 14 I = 264029
3215031751 13
118670087467 9
307768373641 8
315962312077 4
354864744877 3
457453568161 11
528929554561 1
546348519181 5
602248359169 6
1362242655901 2
1871186716981 10
2152302898747 12
2273312197621 0
2366338900801 7
Number of tested functions 130643
execution time : 0.14 s
Output of main() corresponding to ex. 5
---------------------------------------
n 18 I = 1519829
3215031751 10
118670087467 16
307768373641 2
315962312077 12
354864744877 6
457453568161 13
528929554561 14
546348519181 3
602248359169 9
1362242655901 4
1871186716981 1
2152302898747 11
2273312197621 5
2366338900801 8
3343433905957 0
3461715915661 17
3474749660383 7
3477707481751 15
Number of tested functions 756999
execution time : 0.25 s
Output of main() corresponding to ex. 6
---------------------------------------
n 19 Bijection not found.
Number of tested functions 260214998
execution time : 75.738 s
Output of main() corresponding to ex. 7
---------------------------------------
n 20 Bijection not found.
Number of tested functions 2
execution time : 0.000 s