algorithm for functions permutating integers

Question

Hi,

I want to write a function y = f(x) and another function x = g(y) that acts as a reversible, where y = f(g(y)) and where x and y are permutated integers.

For very simple example in the range of integers in 0 to 10 it would look like this: 0->1, 1->2, 2->3,..., 9->10, 10->0 but this is the simplest method by adding 1 and reversing by subtracting 1.

I want to have more sofisticated algorithm that can do something like this: 234927773->4299, 34->33928830, 850033->23234243423 but stil correct reversible conversion can be obtained.

The solution would be obtained with a huge table storing pairs of unique integers but this will not be correct. This must be a function.

Chrisiek

Answer 1

You could use polynomial interpolation methods to interpolate a function one way, then do reverse interpolation to find the inverse function.

Here is some example code in MATLAB:

function [a] = Coef(x, y)
    n = length(x);

    a = y;
    for j = 2:n
        for i = n:-1:j
            a(i) = (a(i) - a(i-1)) / (x(i) - x(i-j+1));
        end
    end
end

function [val] = Eval(x, a, t)
    n = length(x);

    val = a(n);
    for i = n-1:-1:1
       val = a(i) + val*(t-x(i)); 
    end
end

It builds a Divided Difference table and evaluates a function based on Newtons Interpolation.

Then if your sets of points are x, and y (as vectors of the same length, where x(i) matches to y(i), your forward interpolation function at value n would be Eval(x, Coef(x, y), n) and the reverse interpolation function would be Eval(y, Coef(y, x), n).

Depending on your language, there are probably much cleaner ways to do this, but this gets down and dirty with the maths.

Here is an excerpt from the Text Book which is used in my Numerical Methods class: Google Book Link

Answer 2

You could just XOR.

y = x XOR p
x = y XOR p

Though not my area of expertise, I think that cryptography should provide some valuable answers to your question.