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 #include 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 ---------------------------------------------------------------------------------