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