Quickly: How to turn a number into a function

In these recent posts, I have been talking about hunting for functions with certain properties. I decided to try an exhaustive search of a particular function space to find the functions I was looking for, by identifying a 1:1 relationship between numbers and functions, then iterating through all of the numbers and testing the corresponding function.

In brief, I treated the number as an efficient encoding of the truth table for the function. By "efficient", I mean I used an encoding system in which every number in the range represented a valid and distinct truth table, and all possible functions were represented in the range. Since I'm talking about functions that operate on discrete, finite sets of values, the number of truth tables is finite.

First, I used a system I came up with a while ago to represent permutations as numbers. I originally devised this as a way to encode every possible shuffled state of a deck of cards, but it really works for any permutation. Encode the permutation f_a as follows:

R_p(f_a) = N! (f_a:0(0)/N! + f_a:1(1)/(N-1)! + f_a:2(2)/(N-2)! ... f_a:3(N-1)/1!)

Where f_a:n returns the zero-based index of f_a(n) within the ordered set of values returned by f_a(x) where x >= n.

So, for example, the permutation f_a(x) = x + 2 (modulo 4) can be represented as the number 10.  Here's how the encoding works:

f_a:0 returns the zero-based index of f_a(0) in the set [0, 1, 2, 3].  That is, it returns 2, since f_a(0) = 2, and 2 is found at position 2 in the set.

f_a:1 returns the zero-based index of f_a(1) in the set [0, 1, 3].  That is, it returns 2, since f_a(1) = 3, and 3 is found at position 2 in the set.

f_a:2 returns the zero-based index of f_a(2) in the set [0, 1].  That is, it returns 0, since f_a(2) = 0, and 0 is found at position 0 in the set.

f_a:3 returns the zero-based index of f_a(3) in the set [1].  That is, it returns 0, since f_a(3) = 1, and 1 is found at position 0 in the set.

So:

R_p(λx → x + 3) = 4! (2/4! + 2/3! + 0/2! + 0/1!) = 10

In my last post, I treated the function f(a, b) as selecting permutation f_a from an indexed set, and applying it to value b. The N permutations required for distinct values of a can all be encoded together in a single number, as follows:

R_f(f) = R_p(f₀)(N!)⁰ + R_p(f₁)(N!)¹ + ... + R_p(f_N-1)(N!)^N-1

So the function f(x, y) = x + y (modulo 4) can be encoded as follows, given that R_p(f₀) = 0, R_p(f₁) = 1, R_p(f₂) = 10, R_p(f₃) = 3.

R_f(λx, y → x + y) = 0(4!)⁰ + 1(4!)¹ + 10(4!)² + 3(4!)³ = 0 + 24 + 5760 + 41472 = 47256

For my function-space exploration, I simply reversed this process for each number to generate the truth table, and I used the truth table to test for the properties I was looking for.  However, for the fun of it, here is how you would apply the function to a set of values.  Given the function above, you would apply it to the values 2 and 3 as follows:

R_p(f₂) = floor(R_f(f) / (4!)²) % 4! =  floor(47256 / 576) % 4 = 10

f_2:0(0) = floor(4! R_p(f₂) / 4!) % 4 = 2, therefore f₂(0) = 2 (i.e. zero-indexed value 2 from [0, 1, 2, 3])

f_2:1(1) = floor(3! R_p(f₂) / 4!) % 3 =  2, therefore f₂(1) = 3 (i.e. zero-indexed value 2 from [0, 1, 3])

f_2:2(2) = floor(2! R_p(f₂) / 4!) % 2 =  0, therefore f₂(2) = 0 (i.e. zero-indexed value 0 from [0, 1])

f_2:3(3) = floor(1! R_p(f₂) / 4!) % 1 =  0, therefore f₂(3) = 1 (i.e. zero-indexed value 0 from [1])

So 2 + 3 (modulo 4) = 1.

The looooooong way.