3
$\begingroup$

I'm looking for a function where f(x1, x2) = f(x2, x1), but f(x1, x2) CANNOT equal any other f(xi, xj). Also, f() must also be reversible, so I could calculate xi from f(xi, xj) and xj. Can anyone think of such a function?

As an example, f() cannot be bitwise addition: bin3 + bin5 = bin8, but bin1 + bin7 = bin8 also.

edit: Thanks all. I'm just going with f(x1,x2) = implode(delimiter, sort(x1,x2)). I figured maybe there was a more elegant solution. The insights on bounding were good though. I would give upvotes all around but I don't have enough rep yet.

  • 0
    @BlackBear: Probably too trivial for them.2011-11-02

3 Answers 3

1

Your output space needs to be larger than your input space (or both need to be infinite), because for an input space of size N there are N*(N-1)/2+N unordered pairs that must give different outputs.

So, for example, there's no possible C function with the signature int F(int, int) with your desired properties. You either need a larger output type or an unbounded space like a BigInteger.

Assuming you're working with BigInteger, you can turn an ordered pair into an unordered pair by using min(x1,x2) and max(x1,x2). Then you can interleave their digits for the result. Thus:

F(52, 109) = Interleave(min(52,109), max(52,109)) = ...00000015029 = 15029

Given 15029 it is easy to determine it came from 109 and 52. So the reverse function is easy.

6

How about

f(x1, x2) = min(x1, x2) << 32 + max(x1,x2) 

where x1 and x2 are 32 bit integers and the return value is 64 bit. This essentially packs the two 32-bit arguments into one 64-bit value, the smaller one into the most significant bits.

  • 0
    oops, my bad. i added for the shift operator.2011-11-02
2

How about this function:

f(x, y) = {x, y}

  • f(x1, x2) = f(x2, x1)

    holds since sets doesn't care about order

  • f(x1, x2) CANNOT equal any other f(xi, xj)

    holds (apart from the above exception)

  • f must also be reversible

    Holds, since you can just get the first and second element of the set, to find out what the arguments were.

(And it works for arbitrarily large integers.)

If you're having trouble knowing how to store a mathematical set in a file, here's a suggestion:

  • One set per line
  • Each element in the set separated by a , symbol.
  • 0
    Sorting the numbers is a good idea in that case :) Another option is to search for one number first, and then, within that result, search for the other number. Next time, if you have efficiency considerations, state them upfront.2011-11-02