Monday, December 2, 2013

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 fa as follows:

Rp(fa) = N! (fa:0(0)/N! + fa:1(1)/(N-1)! + fa:2(2)/(N-2)! ... fa:3(N-1)/1!)

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

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

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

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

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

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

So:

Rp(λ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 fa 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:

Rf(f) = Rp(f0)(N!)0Rp(f1)(N!)1 + ... + Rp(fN-1)(N!)N-1

So the function f(x, y) = x + y (modulo 4) can be encoded as follows, given that Rp(f0) = 0, Rp(f1) = 1, Rp(f2) = 10, Rp(f3) = 3.

Rf(λx, y → x + y) = 0(4!)0 + 1(4!)1 + 10(4!)2 + 3(4!)3 = 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:

Rp(f2) = floor(Rf(f) / (4!)2) % 4! =  floor(47256 / 576) % 4 = 10

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

So 2 + 3 (modulo 4) = 1.

The looooooong way.