In my last hurried post, I mentioned that I carried out a brute-force exploration of the function-space I was looking at, looking for functions with certain properties. I'm sure the technique I used is well-known, and there are probably better ways to do it, but I thought I would describe what I did anyway.
The functions I was looking at were invertible, so if there was a function f (a, b), then there had to exist another function g (a, c) such that g (a, f (a, b)) = b. In this case, all values are drawn from the set N.
Because of the invertibility requirement, we can say that any function fa (b) = f (a, b) is a permutation of |N| values, so the number of distinct functions fa is |N|!. If we think of f (a, b) as selecting a function fa from a table of values using the index a and applying that function to the value b, then the number of distinct tables of |N| functions drawn from a set of size |N|! is (|N|!)|N|.
That means for |N| = 4, for example, I needed to check (4!)4 = 331776 functions for those that had the additional commutative property I was looking for.
In order to check all of the functions exhaustively, I came up with a 1:1 relationship between every number in [0..331775] and every function in the set. Then I iterated through each number, generated the function from the number, and tested the function for the property I was looking for.
But parenting duties call again, so I'll have to finish this later.
No comments:
Post a Comment