# reversible, reflexive function with unique cardinality

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.

-

## migrated from stackoverflow.comNov 2 '11 at 23:30

This question came from our site for professional and enthusiast programmers.

What is the domain of the function? Integers? – Szabolcs Nov 2 '11 at 15:02
any real number, but I could restrict it to integers if the solution was elegant. – Dave Lo Nov 2 '11 at 15:09
What is 'mathematical notation' if not 'text/numerics'? What are the actual constraints on the domain and range of this function you seek? Right now, the formatted string f({textual representation of x1 goes here}, {textual representation of x2} goes here) meets your stated requirements, such as they are... – AakashM Nov 2 '11 at 15:09
@AakashM: Indeed, the duality between text/numerics and mathematics is the core of Gödel's rather famous incompleteness theorem. Have a +1 for your comment. – Donal Fellows Nov 2 '11 at 15:12
@BlackBear: Probably too trivial for them. – Donal Fellows Nov 2 '11 at 15:17

## 3 Answers

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.
-
f(xi, xj) has to be storable & searchable as text/numerics, so it can't be something based on merely mathematical notation (added this restriction to question) – Dave Lo Nov 2 '11 at 14:56
I'm sure you can find out a good way of storing a set as text / numbers, no? – aioobe Nov 2 '11 at 14:57
This representation of set is not unique. You could sort the elements, which then yields essentialy the solution in my answer. – Henrik Nov 2 '11 at 15:03
Actually, f(x1,x2) = implode(delimiter, sort(x1,x2)) is one possible solution. – Dave Lo Nov 2 '11 at 15:07
@Henrik, What gave you the impression that the on-file representation needs to be unique? Your solution on the other hand have the obvious limitation of bounded integers, which is not stated in the question. In fact, judging from the original tags, it seems like this is more a mathematical problem, in which case bounded integers are quite unusual. – aioobe Nov 2 '11 at 15:09

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.

-

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.

-
what is your << operand? (casting?) – Dave Lo Nov 2 '11 at 14:54
<< 32 means "multiply by 2^32". – aioobe Nov 2 '11 at 14:55
It's the shift operator. – Henrik Nov 2 '11 at 14:55
doesn't work. f(1,7) = 4294967304, but so does f(5,3) – Dave Lo Nov 2 '11 at 15:03
f(1,7) = 4294967303, f(5,3) = 12884901893 – Henrik Nov 2 '11 at 15:06