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.

  • 2
    What is the domain of the function? Integers?2011-11-02
  • 1
    any real number, but I could restrict it to integers if the solution was elegant.2011-11-02
  • 3
    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...2011-11-02
  • 0
    @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.2011-11-02
  • 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
    what is your << operand? (casting?)2011-11-02
  • 0
    `<< 32` means "multiply by 2^32".2011-11-02
  • 0
    It's the shift operator.2011-11-02
  • 0
    doesn't work. f(1,7) = 4294967304, but so does f(5,3)2011-11-02
  • 0
    f(1,7) = 4294967303, f(5,3) = 128849018932011-11-02
  • 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
    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)2011-11-02
  • 2
    I'm sure you can find out a good way of storing a set as text / numbers, no?2011-11-02
  • 0
    This representation of set is not unique. You could sort the elements, which then yields essentialy the solution in my answer.2011-11-02
  • 0
    Actually, f(x1,x2) = implode(delimiter, sort(x1,x2)) is one possible solution.2011-11-02
  • 0
    @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.2011-11-02
  • 0
    @aioobe - it should be searchable, so {1,7} must be found whether it's stored as 1, 7 or 7, 1. So a unique representation would at least be helpful.2011-11-02
  • 0
    Gets messy if you encode f(x,x). Not that that's impossible to circumvent, but it's still messy.2011-11-02
  • 0
    Well search using, say, `grep "{1,7}|{7,1}"` then... What's the problem?2011-11-02
  • 0
    @DonalFellows, true. A [multiset](http://en.wikipedia.org/wiki/Multiset) would probably be more appropriate actually.2011-11-02
  • 0
    f(x1,x2) = implode(delimiter, sort(x1,x2)) is the solution i'm going with.2011-11-02
  • 0
    @aioobe the problem with searching for both is that there will be massively more searches (reads) than inserts (writes). Because of the system design, most searches are expected to return a null set, which means that by searching for both versions, the search has to run twice nearly always.2011-11-02
  • 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